Problem Description

Desmond the Moonbear is stuck on the moon. He does not know how he got there. Help him get home

The moon is linear. Desmond starts from position 0 and wants to go home to position n [in metres]

It takes him 1 second to move 1 metre on the moon [The gravity is very low]

There are c magical craters on the moon. Each crater starts from position si and ends at position ei and takes ti time to transverse [Warning: ti is not necessarily smaller than ei-si+1]

Desmond is afraid of the dark, so he is willing to go through at most m craters

No 2 craters will intersect due to spacing considerations [for 2 distinct integers i and j, if si<sj, ei<sj]

No crater will end after Desmond's house [i.e. for all i, si<n]


The first line of the input consists of 3 integers, n, m and c

Next c lines of input consists of 3 integers per line, si, ei and ti

No 2 craters will intersect [for 2 distinct integers i and j, if si<sj, ei<sj]

All craters will be given in sorted starting order


A single integer t representing the minimum amount of time Desmond will take to get home.


Subtask 1 (15%) n<=1000,c<=10

Subtask 2 (30%) n<=1000000,c<=1000

Subtask 3 (55%) n<=1000000000,c<=1000000

Subtask 4 (0%) will be the sample testcases

Sample Testcase 1


6 1 2
1 3 4
3 5 1


Desmond walks from position 0 to position 3, taking 3 time.

Desmond takes tunnel 2, taking 1 time and ending up at position 5.

Desmond walks from position 5 to position 6 [home], taking 1 time.

Therefore, Desmond took 5 time