Maximizing Quest Rewards

You are playing a computer game named Quests in which you must complete n quests. Completing each quest always awards you its base experience points (XPs) given by x. In addition, each quest has a target difficulty level d and a bonus mechanism: if you complete a quest when your current level is less than d, you receive c times the base XPs for that quest; otherwise, you receive only the base XPs.

Your level is determined by the total XPs you have earned. Formally, if you have accumulated a total of T XPs, then your level is the largest integer L such that \[ L\;\text{such that}\; T \ge L \cdot v \] (that is, you are at level L if and only if T is less than (L+1)\cdot v and at least L\cdot v).

You know all n quests in advance. The i-th quest is described by two numbers: x_i (the base XP awarded) and d_i (the target difficulty level). When you attempt a quest, if your current XP is less than d_i\cdot v (i.e. your level is below d_i), you earn c × x_i XPs; otherwise, you earn just x_i XPs.

You are skilled enough to complete the quests in any order. Your goal is to plan an ordering of the quests so that you can achieve the maximum possible total XPs. Note that since you always earn the base XP x_i regardless of when you complete a quest, the problem reduces to selecting a subset of quests on which you can obtain the bonus (thus gaining an extra (c-1) × x_i XP for each such quest) while still obeying the following condition: 

If you decide to complete a quest with bonus, then at the time of completing that quest, your current XP (which is the sum of c × x for all bonus quests completed earlier) must be strictly less than d × v of that quest. In other words, if you plan to take a quest with parameters (x,d) with bonus, and if you have already completed some bonus quests accumulating a total bonus contribution of B (so that the XP earned from bonus quests is c × B), then you can take this quest with bonus only if \[ c \times B

After you complete all quests (performing bonus on some and normal on the rest), your final XP will be [ T = S + (c-1) \times B, ] where S is the sum of all x values and B is the total base XP of the quests for which you managed to get the bonus.

Given the values of n, v, and c, and the list of quests (x and d for each quest), determine the maximum total XP you can achieve.

Input Format: The input begins with three integers n, v, and c. This is followed by n lines, each containing two integers x and d representing a quest’s base XP and target difficulty level respectively.

Note: You always complete all quests; the challenge is to decide on which quests you can obtain the bonus without violating the requirement that, before performing a bonus quest with target d, your accumulated bonus XP (when multiplied by c) is strictly less than d × v.

inputFormat

The first line contains three integers: n (1 ≤ n ≤ 16), v and c (c > 1). Each of the next n lines contains two integers x and d, where x (a positive integer) is the base XP of a quest and d (at least 1) is its target difficulty level.

You may assume that the total base XP S is not more than 10⁴ and other parameters are chosen so that a solution using bitmask dynamic programming is feasible.

outputFormat

Output a single integer, the maximum total XP that can be earned after completing all quests in an optimal order.

sample

3 10 2
15 1
2 2
9 3

43