Hiding Acorns

Time limit1sMemory limit128 MB

Summary

Given K arithmetic-progression rules marking boxes, find the box number where the D-th acorn is placed, counting boxes in increasing order.

Level: Medium6 of 10
Topics: Binary search, Prefix sum, Math
Solved: No attempts yet

Problem

Suhyeong won $D$ acorns as the first prize at the HEPC contest. To keep the other squirrels from taking them, he hides every acorn in $N$ boxes numbered 1 through $N$ .

There are too many boxes for him to remember which ones hold acorns, so he writes rules instead. A rule is three numbers $A$ , $B$ , $C$ , and it means put one acorn into box $A$ , box $A+C$ , box $A+2C$ , and so on, using every such box that does not go past box $B$ . He is afraid that one rule gives away everything, so he writes $K$ of them.

For example, take a rule that runs from box 100 to box 150 in steps of 10 and a rule that runs from box 110 to box 150 in steps of 15. Acorns then go into boxes 100, 110, 120, 125, 130, 140 and 150, and boxes 110 and 140 hold two acorns each.

A box holds any number of acorns. Suhyeong fills the positions marked by the rules one acorn at a time, in increasing order of box number, until all $D$ acorns are placed. Print the number of the box that receives the last acorn.

Input

The first line contains the number of boxes $N$ , the number of rules $K$ and the number of acorns $D$ , separated by spaces. ( $1 \le N \le 1{,}000{,}000$ , $1 \le K \le 10{,}000$ , $1 \le D \le 1{,}000{,}000{,}000$ )

Each of the next $K$ lines contains three integers $A$ , $B$ and $C$ describing one rule, separated by spaces. ( $1 \le C \le A \le B \le N$ )

$D$ is at most the total number of positions marked by the rules.

Output

Print the number of the box that receives the last acorn.

Examples3

Example 1
Input
```
200 2 5
100 150 10
110 150 15
```
Expected output
```
125
```
Example 2
Input
```
1 1 1
1 1 1
```
Expected output
```
1
```
Example 3
Input
```
10 1 4
2 9 2
```
Expected output
```
8
```