Tinder

Alex wants to get a girlfriend. He discovered a dating app similar to Tinder. The app shows Alex $N$ different girls. He can swipe left or right on their photo. If he swipes right on a photo of a certain girl and she swipes right on his, then they match and can start chatting in the app.

Because he did not purchase the pro version, Alex has a limited number of right swipes. The app estimates for each girl the probability that she will swipe right on Alex. Moreover, the app will decrease the number of available swipes by a different value depending on the girl Alex swipes right on.

Help Alex find out what is the maximum expected number of matches he can get.

Input data

The first line of the input contains the values $N$ and $X$, representing the number of girls shown to Alex and the maximum number of right swipes.

The following $N$ lines will contain data about the girls.

The $i^{th}$ line will contain values $p_i$ and $q_i$, representing the probability that the $i^{th}$ girl will swipe right on Alex and the value subtracted from the total number of available swipes if Alex swipes right on the $i^{th}$ girl. Every $p_i$ value will be an integer between $0$ and $100$, representing the probability as percentage.

Output data

The output will contain an integer that represents the maximum expected number of matches as a percentage.

Constraints and clarifications

• $1 \leq N \leq 5 \ 000$
• $1 \leq X, q_i \leq 10^4$
• For tests worth $10$ points, $1 \le N \le 20$.
• For tests worth extra $40$ points, $1 \le N \cdot X \le 10^6$.

Example 1

stdin

6 3
70 1
54 3
20 1
9 1
20 2
33 1

stdout

123

Explanation

If Alex swipes right on the first, the third and the sixth girls then the expected number of matches he will get is equal to $1 \cdot 70$ + $1 \cdot 20$ + $1 \cdot 33$ = $123$. It turns out that this is the best he can do.