#P17042. [SGU553] Sultan's Pearls

[SGU553] Sultan's Pearls

题目描述

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

最初,前 n−mn-m 颗珍珠放在桌面上,后 mm 颗珍珠悬在桌边。

第 ii 颗珍珠的质量为 wiw_i,价值为 cic_i。

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

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

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

Wh≤kWtW_h\le kW_t,

其中 kk 是摩擦系数。

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

输入格式

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

接下来 nn 行,第 ii 行包含两个整数 wi,ciw_i,c_i,分别表示第 ii 颗珍珠的质量和价值。

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

输出格式

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

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

数据范围

  • 2≤n≤2×1052\le n\le 2\times 10^5;
  • 1≤m<n1\le m<n;
  • 1≤k≤101\le k\le 10;
  • 1≤wi,ci≤10001\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