Problem D
Networking

Gustaf will graduate next year and needs to choose his final courses to study before starting his thesis project. Each course provides a certain number of credits, but as a true academic weapon, he already has more than enough credits to graduate. His real goal is to study as much as possible, but the university has blocked him from studying more than $K$ credits because it is becoming too expensive.

Gustaf now needs your help to figure out which courses to take to maximize the amount of credits without breaking the university’s limit. "Easy!", you say, "I learned this in algodat!". But Gustaf has an additional requirement. Each course has a lecturer, and he does not want to take two courses given by the same lecturer (each new lecturer he meets is a new potential connection on LinkedIn!).

Of course, he could have done it himself, with all the courses he has taken he is more than capable, but he is waiting for an important email and is afraid that he will miss it if he looks away.

Input

The first line contains two integers, the number of courses $1 \le N \le 10^3$, and the maximum amount of credits he can take $1 \le K \le 10^4$. Each of the next $N$ lines describe a course by giving its credits $1 \le d \le K$, followed by a string $s$, the name of the lecturer. The strings only contain lowercase characters between ’a’ and ’z’, and are between $1$ and $10$ characters in length.

Output

Output the maximum amount of credits $\le K$ that Gustaf can take without taking two courses with the same lecturer.

Scoring

3 10
1 tyko
2 maj
5 tyko

7

8 100
79 per
43 viktor
94 anna
91 carl
25 per
31 anna
70 anna
12 viktor

99