题目描述

苏丹苏莱曼拥有一串珍贵的珍珠。这串珍珠共有 $n$ 颗，按从桌面一端到悬空一端的顺序编号为 $1,2,\ldots,n$。

最初，前 $n-m$ 颗珍珠放在桌面上，后 $m$ 颗珍珠悬在桌边。

第 $i$ 颗珍珠的质量为 $w_i$，价值为 $c_i$。

仆人每天可以从珍珠串的某一端偷走恰好一颗珍珠：

• 从悬空端取走一颗珍珠。取走后，需要把珍珠串向桌边外拉动一颗，使得仍然恰好有 $m$ 颗珍珠悬空；
• 从桌面端取走一颗珍珠。此时悬空部分保持不动。

设当前悬空的 $m$ 颗珍珠总质量为 $W_h$，仍在桌面上的珍珠总质量为 $W_t$。为了保证珍珠串不会滑落，每次操作结束后都必须满足

$W_h\le kW_t$，

其中 $k$ 是摩擦系数。

仆人可以在任意时刻停止偷取珍珠。请计算在始终保证珍珠串不会滑落的前提下，他最多能够偷到总价值为多少的珍珠。

输入格式

第一行包含三个整数 $n,m,k$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $w_i,c_i$，分别表示第 $i$ 颗珍珠的质量和价值。

保证初始状态下珍珠串不会滑落。

输出格式

输出一个整数，表示仆人能够偷取的珍珠的最大总价值。

如果一颗珍珠也不能偷，则输出 0。

数据范围

• $2\le n\le 2\times 10^5$；
• $1\le m<n$；
• $1\le k\le 10$；
• $1\le w_i,c_i\le 1000$。

样例 1

样例输入

5 2 1
5 3
4 2
6 4
3 2
2 2

样例输出

5

样例 2

样例输入

20 7 2
3 4
8 4
8 5
6 14
5 10
3 18
2 5
2 4
1 6
3 11
4 3
3 5
2 8
4 6
9 14
7 2
7 6
6 4
8 2
10 5

样例输出

60