Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Time Travel
Time Limit: 1000MSMemory Limit: 131072K
Total Submissions: 4060Accepted: 620

Description

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.

Input

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

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

30

Source

[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