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 si-ei+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]
Input
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
Output
A single integer t representing the minimum amount of time Desmond will take to get home.
Subtasks
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
Input
6 1 2
1 3 4
3 5 1
Output
5
Explanation
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