1338 - Invinsible

問題

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

• モンスターは $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$
• 入力はすべて整数である。

入出力例

入力例１

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

出力例１

8

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

---

入力例２

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

出力例２

14

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

---

入力例３

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

出力例３

36

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

---

入力例４

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

出力例４

149