Best Deal

Time Limit: 1 Second    Memory Limit: 32768 KB

Tom, a young explorer, visited an Indian tribe and fell in love with the Chief's daughter. Tom asked the Chief to marry his daughter to him. But the Chief would accept his proposal only if he could provide 10000 golden coins as the engagement gift. Tom couldn't make it, so he pled for a reduction. The Chief said:" OK, I would then request 8000 golden coins if you could get me the fur coat of the Pontiff. Or, if you could get me his crystal, I could drop to 5000 golden coins."

Tom then went to the Pontiff for his fur coat or crystal. The Pontiff too requested some amount of golden coins as the exchange, or a possible reduction of price if Tom could get him some other things. Tom continued to visit other people and found that all of them would either request some golden coins for exchange, or drop the price down for something else.

Now Tom needs your help on trading to marry the girl he loves.

An important rule Tom has to tell you is: the hierachical system is so strict in this tribe that two people will never contact each other in any way if the difference of the two levels they belong to is larger than a certain threshold. Tom is an outsider so he is beyond this restriction. However, if he trades with someone in a lower level, then others in a higher level will not trade with him anymore since otherwise they would be indirectly contacting the lower levels, and vice versa. Therefore your best suggestion to him must have all the situations considered.

For the sake of convenience, let us mark all the trading objects by numbers starting from 1. The Chief's approval is as well considered an object and is always marked 1. Each object has a price P, the owner's level L, and a sequence of substitutions Ti and the corresponding "voucher" price Vi. There must be no "indirect trading" if the difference between two levels is greater than M. You must calculate the least number of golden coins Tom needs to marry the daughter of the Chief.

Input

The input consists of several test cases. For each test case:

The 1st line contains two integers M and N (1<=N<=100) which represent the threshold of level difference and the total number of trading objects respectively.
Then the descriptions of N objects follow, in the increasing order with respect to their marks. Each description begins with three nonnegative integers P, L, and X.

Output

For each test case, print in a single line the minimum number of golden coins needed.

Sample Input

1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0

Sample Output

5250

Submit

Source: Zhejiang University Local Contest 2002