Problem Description

There are $ N $ types of activities, activity $1,\ 2,\ \dots\ N$. You can choose one or more from these activities and perform them in any order. However, you cannot perform the same activity more than once.

Your current stamina is $ H $. Performing activity $ i $ will earn you [MATH4] points, and then your stamina will decrease by $ b_i $ (it is allowed for your stamina to become less than $ 0 $ after an activity).
Find the maximum total score you can achieve.

Input Format

The input is given from the standard input in the following format:

$ N $ $ H $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $\vdots$ $ a_N $ $ b_N $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

4 6
4 1
3 2
2 3
1 4

Sample Output #1

45

Sample Input #2

4 6
1 1
2 2
3 3
4 4

Sample Output #2

30

Sample Input #3

16 100
18 17
5 18
7 2
5 8
6 2
16 16
2 18
13 17
18 10
11 10
17 8
1 2
20 7
4 11
7 15
2 1

Sample Output #3

9282

Notes/Hints

Note

Discussion of this problem is prohibited until 2021/4/24 18:00 JST. If mentioned, legal action may be taken. It is okay to publish the total score and certification level after the exam, but please do not disseminate information about which problems were solved.

Constraints

• All inputs are integers.
• $1\ \leq\ N\ \leq\ 100$
• $1\ \leq\ H\ \leq\ 10^5$
• $1\ \leq\ a_i,\ b_i\ \leq\ 10^5$

Sample Explanation 1

For example, the total score can be $ 45 $ points by doing the following: - Initially, stamina is $ 6 $. - Perform activity $ 1 $. Earn $4\ \times\ 6\ =\ 24$ points, and stamina becomes $6\ -\ 1\ =\ 5$. - Perform activity $ 2 $. Earn $3\ \times\ 5\ =\ 15$ points, and stamina becomes $5\ -\ 2\ =\ 3$. - Perform activity $ 3 $. Earn $2\ \times\ 3\ =\ 6$ points, and stamina becomes $3\ -\ 3\ =\ 0$.

见题面 Input 部分

见题面 Output 部分