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.

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

30

Source

POJ Monthly--2006.08.27, Dagger