Hiding Acorns

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.

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.

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