题目描述

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

特别的是，小蓝可以使用一个魔法（最多使用一次），将某一件物品的重量增加 $K$，同时该物品的价值翻倍。当然，小蓝也可以选择不使用魔法。

请你帮她计算，在背包承重不超过 $M$ 的前提下，她最多可以获得多大的物品总价值。

输入格式

第一行输入三个整数 $N, M, K$，分别表示物品数量、背包最大承重、和魔法的重量增加值。

接下来 $N$ 行，每行两个整数 $W_i, V_i$，表示第 $i$ 件物品的重量与价值。

输出格式

一个整数代表答案。

样例输入

3 10 3
5 10
4 9
3 8

样例输出

26

说明

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