問題
宝石店に $N$ 個のケースが横一列に並んでいます。
左から $i \ (1 \leq i \leq N)$ 番目のケースをケース $i$ とします。
この宝石店には $M$ 個の宝石が販売されています。
$j \ (1 \leq j \leq M)$ 個目の宝石の価値は $v_j$ であり、ケース $p_j$ に入れられています。
強盗であるもけちゃんは、連続したちょうど $L$ 個のケースを選び、その中に入っている宝石を全て盗みます。
選んだ $L$ 個のケースすべてに宝石が入っている必要はありません。
このとき、もけちゃんが盗み取ることのできる宝石の価値の総和の最大値を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $M$ $L$ $p_1$ $v_1$ $p_2$ $v_2$ $\vdots$ $p_M$ $v_M$
出力
最大値を出力せよ。
出力の末尾には改行を入れること。
制約
- $1 \leq N \leq 10^9$
- $1 \leq M \leq min(N, 10^3)$
- $1 \leq L \leq min(N, 10^3)$
- $1 \leq p_j \leq N$
- $p_j \neq p_k \ (j \neq k)$
- $-10^7 \leq v_j \leq 10^7$
- 入力は全て整数である。
入出力例
入力例１
12 7 4 5 1 7 5 1 3 3 1 11 2 4 4 10 9
出力例１
14
ケース $7 \ ～ \ 10$ を選ぶのが最適です。
入力例２
6 2 5 1 -10 2 -10
出力例２
-10
ケース $2 \ ～ \ 6$ を選ぶのが最適です。
入力例３
28 17 7 3 85 16 74 20 -22 7 0 11 86 5 -8 1 67 10 -30 6 36 21 83 19 53 4 41 17 -58 28 43 13 93 27 34 23 -17
出力例３
223