005 - Sand of Star

時間制限 2 秒 / メモリ制限 256 MB / 得点 500 / x 9 /


TLE
2sec
MLE
256MB
得点
500

問題

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

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

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

入力

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

N M K
P
L1 R1 C1
L2 R2 C2

LP RP CP

出力

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

制約

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

  • 1N109
  • 1Pmin
  • 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