Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Time Travel
Time Limit: 1000MSMemory Limit: 131072K
Total Submissions: 4126Accepted: 627


According to Professor Canaried’s recent theory about space and time, our universe is like a piece of plane paper with infinite length and finite width, if we consider time as X-dimension of plane and space as Y-dimension. Outside the boundary of our universe are dangerous unknown spaces, which once people reach, he/she can never come back to our universe. People cannot go back to the foretime but can go forward to the future freely.

Dagger is now at time0 and position0, she wants to move to timeN and positionM. Time Travel Company supplies K various services; each can be described as three integers a, b, c, which means if you are at timeX and positionY now, you can move to timeX + a and positionY + b for c Gils’ cost. Your task is to find the minimal cost for Dagger to move to timeN and positionM. The costs are always positive.


There are several test cases in the input. Each test case starts with three integers N (0 < N ≤ 100), M (0 < M ≤ 100) and K (0 ≤ K ≤ 100). The Next K lines each contains three integers a, b, c. N = M = K = 0 indicates the end of the input which should not be processed.


Output one line for each test case in the input, the minimal cost. Output −1 if it is impossible to move to the destination.

Sample Input

4 6 3
4 6 100
1 5 10
3 1 20
0 0 0

Sample Output



[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator