问题描述

小蓝面前有 $N$ 件物品, 其中第 $i$ 件重量是 $W_i$， 价值是 $V_i$。她还有一个背包, 最大承重是 $M$。

小蓝想知道在背包称重范围内, 她最多能装总价值多少的物品?

特别值得一提的是, 小蓝可以使用一个魔法 (总共使用一次), 将一件物品的重量增加 $K$, 同时价值翻倍。(当然小蓝也可以不使用魔法)

输入格式

第一行包含 3 个整数 $N, M$ 和 $K$。

以下 $N$ 行, 每行两个整数 $W_i$ 和 $V_i$。

输出格式

一个整数代表答案。

3 10 3
5 10
4 9
3 8

26

样例说明

选择第二件和第三件物品, 同时对第二件物品使用魔法。

评测用例规模与约定

对于 30% 的数据, $1 \leq N, M, K \leq 100$。

对于 100% 的数据, $1 \leq N \leq 2000,1 \leq M, K \leq 10000,0 \leq W_i, V_i \leq 10000$。