Problem Description

In the final round of CODE FESTIVAL 2015, there was a person who did an interesting action by standing with a large paper that said "Genius", making everyone laugh. Therefore, it was decided that all $ N $ participants of the final round of CODE FESTIVAL 2018 would do the same action and take a group photo.

Each person has two values: "neatness of handwriting" and "interestingness of face". The "neatness of handwriting" of the $ i $-th person is $ a_i $, and the "interestingness of face" is $ b_i $. The "likability of the photo" is the sum of (neatness of handwriting) × (interestingness of face) for all people.

The participants want to maximize the "likability of the photo". They cannot change the "interestingness of face", but if a person trains once, their "neatness of handwriting" increases by 1. The total number of training sessions for all people must not exceed $ X $. Find the maximum value of the likability of the photo.

Input Format

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

$ N $ $ X $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ a_3 $ $ b_3 $ $ : $ $ : $ $ a_N $ $ b_N $

Output Format

Output the maximum value of the likability of the photo.

Sample Input and Output

Sample Input #1

3 1
12 10
24 20
36 5

Sample Output #1

800

Sample Input #2

3 0
25 20
17 30
9 50

Sample Output #2

1460

Sample Input #3

3 3
3 25
5 12
7 25

Sample Output #3

385

Notes/Hints

Constraints

• $ N $ is an integer between 1 and 100 inclusive.
• $ X $ is an integer between 0 and 100 inclusive.
• $a_i,\ b_i\ (1\ \leq\ i\ \leq\ N)$ are integers between 1 and 100 inclusive.

Sample Explanation 1

Since $ X=1 $, the number of training sessions allowed is 1. Therefore, the following four methods are considered:
- If no one trains: the likability of the photo is $12\ \times\ 10\ +\ 24\ \times\ 20\ +\ 36\ \times\ 5\ =\ 780$
- If the 1st person trains once: the likability of the photo is $13\ \times\ 10\ +\ 24\ \times\ 20\ +\ 36\ \times\ 5\ =\ 790$
- If the 2nd person trains once: the likability of the photo is $12\ \times\ 10\ +\ 25\ \times\ 20\ +\ 36\ \times\ 5\ =\ 800$
- If the 3rd person trains once: the likability of the photo is $12\ \times\ 10\ +\ 24\ \times\ 20\ +\ 37\ \times\ 5\ =\ 785$
Thus, the maximum value of the likability of the photo is $ 800 $.

Sample Explanation 2

Since $ X=0 $, no one can train. Therefore, the likability of the photo is $25\ \times\ 20\ +\ 17\ \times\ 30\ +\ 9\ \times\ 50\ =\ 1460$.

Sample Explanation 3

For example, if the 1st person trains 2 times and the 3rd person trains 1 time, the likability of the photo $ 385 $ can be achieved. Also, it is not possible to make the likability of the photo greater than $ 385 $.

见题面 Input 部分

见题面 Output 部分