1338 - Invinsible

時間制限 2 秒 / メモリ制限 512 MB / 得点 100 / Writer もけ / x 3 / 統計 /


TLE
2sec
MLE
512MB
得点
100

問題

魔法使いのもけちゃんが一体のモンスターと戦っています。
もけちゃんは未来予知能力により、以下のことが分かっています。

  • モンスターは $N$ 回攻撃を仕掛けてくる。
  • モンスターは時刻 $t_i$ に威力 $d_i$ $(1 \leq i \leq N)$ の攻撃を仕掛けてくる。

もけちゃんは時間 $T$ の間モンスターの攻撃を無効化する魔法を使うことができます。
しかし、もけちゃんの残りの魔力では、$0$ 回以上 $K$ 回以下しかこの魔法を使うことができません。
最適に魔法を使うことで、モンスターから受ける攻撃の威力の合計を最小化してください。

入力

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

$N$ $T$ $K$
$t_1$ $d_1$
$t_2$ $d_2$
$\vdots$
$t_N$ $d_N$

出力

モンスターから受ける攻撃の威力の合計の最小値を出力せよ。
出力の末尾には改行を入れること。

制約

  • $1 \leq N \leq 10^3$
  • $0 \leq T \leq 10^9$
  • $0 \leq K \leq 10^3$
  • $0 \leq t_i \leq 10^9$
  • $0 \leq d_i \leq 10^5$
  • 入力はすべて整数である。

入出力例

入力例1

8 5 2
10 2
2 1
1 4
12 1
3 3
8 9
13 10
5 8

出力例1

8

例として、時刻 $4$ ~ 時刻 $8$、時刻 $10$ ~ 時刻 $14$ に魔法を使うことで、最小値 $8$ を得ることができます。


入力例2

5 1933 0
1933 3
1933 1
1933 4
1933 1
1933 5

出力例2

14

魔法を一度も使うことができません。
同じ時刻に重複して攻撃を仕掛けてくることもあります。


入力例3

10 0 1000
3 9
10 4
5 8
5 1
9 4
0 0
8 7
10 2
2 1
9 0

出力例3

36

魔法による効果が発揮される時間が $0$ であることもあります。


入力例4

20 17 3
31 94
13 22
13 29
85 39
64 17
65 66
14 39
55 40
95 29
86 97
16 14
10 10
34 73
50 37
15 35
27 89
61 91
36 99
85 63
90 83

出力例4

149