1493 - Sand of Star

問題

山本君は「アルゴリズムバトル」というゲームに夢中である。
このゲームでは明日から (今日を $0$ 日目としたとき、$1$ 日目の初めから) $N$ 日間イベントが開催され、開催中にゲームをプレイするとアイテムを手に入れることができる。
イベント開催中は通常、$1$ 日に入手することのできるアイテムの個数の上限は $M$ 個であり、$0$ 個以上 $M$ 個以下の任意の個数のアイテムを入手することができる。
アイテムを $K$ 個集めると限定カードと交換することができる。

$1$ 日に入手することのできるアイテムの個数の上限が変化する期間が $P$ 個あることが公式サイトで発表されている。
期間 $i$ $(1 \leq i \leq P)$ は、今日を $0$ 日目として、$L_i$ 日目の初めから $R_i$ 日目の終わりまで続き、期間中は毎日、一日にもらえるアイテムの個数の上限が $C_i$ 個となる。

山本君はどうしても限定カードを手に入れたい。
しかし、山本君も暇ではないため、できる限り短い日数でアイテムを $K$ 個集めたい。
また、ゲームをプレイする日は全て 連続 しているようにしたい。
これらの希望に沿ってゲームをプレイするとき、山本君が限定カードの交換に必要な $K$ 個のアイテムを手に入れるために必要な日数は最短で何日間となるか求めよ。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $K$
$P$
$L_1$ $R_1$ $C_1$
$L_2$ $R_2$ $C_2$
$\vdots$
$L_P$ $R_P$ $C_P$

出力

山本君が $K$ 個のアイテムを手に入れるために必要な日数の最小値を出力せよ。
出力の末尾には改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq N \leq 10^9$
• $1 \leq P \leq \min(10^5, N)$
• $1 \leq L_i \leq R_i \leq N$ $(1 \leq i \leq P)$
• $R_i \lt L_{i + 1}$ $(1 \leq i \leq P - 1)$
• $1 \leq M, C_i \leq 10^5$
• $1 \leq K \leq 10^9$
• 必ず $K$ 個のアイテムを集めることができる
• 入力はすべて整数である

入出力例

入力例1

5 1 5
1
2 3 2

出力例1

3

$1$ 日に手に入れることができるアイテムの個数を表にまとめると、以下のようになる。

1日目	2日目	3日目	4日目	5日目
1	2	2	1	1

このとき、$1$ 日目 ～ $3$ 日目の $3$ 日間と、$2$ 日目 ～ $4$ 日目の $3$ 日間でアイテムを $5$ 個集めることができる。
これよりも短い日数でアイテムを $5$ 個集めることはできないため、$3$ が答えである。
なお、$2$ 日目 ～ $3$ 日目と $5$ 日目にゲームをプレイすることでもアイテムを $5$ 個集めることができるが、これはゲームをプレイする日が連続していないため、このような日の選び方はしてはならない。

---

入力例2

10 5 15
3
4 7 1
8 8 10
9 10 1

出力例2

3