#### Registered Users Only

Please login to view and utilize this feature.

## 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 1Output

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 0 to position 6 [home], taking 1 time.

Therefore, Desmond took 5 time

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 15 | 10 | 2s | 32MB | Minimum |

2 | 30 | 10 | 2s | 32MB | Minimum |

3 | 55 | 10 | 2s | 32MB | Minimum |

4 | 0 | 1 | 2s | 32MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o moonwalk -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512