小藍(lán)面前有 N 件物品，其中第 i 件重量是 W_i，價(jià)值是 V_i。她還有一個(gè)背包，最大承重是 M。

小藍(lán)想知道在背包稱重范圍內(nèi)，她最多能裝總價(jià)值多少的物品？

特別值得一提的是，小藍(lán)可以使用一個(gè)魔法，將一件物品的重量增加 K，同時(shí)價(jià)值翻倍。(當(dāng)然小藍(lán)也可以不使用魔法）

第一行包含 3 個(gè)整數(shù) N、M 和 K。

以下 N 行，每行兩個(gè)整數(shù) W_i 和 V_i。

3 10 3
5 10
4 9
3 8

26

選擇第二件和第三件物品，同時(shí)對第二件物品使用魔法。

對于 30% 的數(shù)據(jù)，1 ≤ N, M, K ≤ 100.

對于 100% 的數(shù)據(jù)，1 ≤ N ≤ 2000, 1 ≤ M, K ≤ 10000, 0 ≤ W_i , V_i ≤ 10000.