Forming Pure Professional Groups

In the Kingdom of Blue Bridge, the king commands a mighty army made up of (n) squads, where each squad consists of soldiers of the same profession. Specifically, the (i)th squad has (b_i) soldiers of profession (a_i). Due to an unexpected storm, the soldiers’ ordering got mixed up. The king wishes to select some soldiers from this shuffled lot and form (k) "pure professional groups" for a grand review. A pure professional group is defined as a team of exactly 3 soldiers sharing the same profession.

Your task is to determine the minimum number of soldiers that must be chosen to guarantee that it is possible to form at least (k) pure professional groups, no matter how unfavourably the soldiers’ professions are distributed among the chosen ones.

Note: Even though the soldiers come from existing squads, soldiers of the same profession from different squads are indistinguishable. If it is impossible to form (k) groups from the available soldiers, output -1.

Hint (Pigeonhole Principle): In order to avoid forming a group, an adversary could choose at most 2 soldiers of each profession. To allow a group to form, picking one more soldier in some profession might force the formation of a triplet. More generally, for any profession with a total of (T) soldiers, note that if you select (x) soldiers from that profession, the number of groups you can form is (\lfloor x/3 \rfloor). An adversary, trying to delay reaching (k) groups overall, will try to keep the count in each profession below a threshold. The careful distribution leads to the following method to compute the answer:

1. Group the squads by profession. For each profession with total count (T), note that you can take at most (\min(T,2)) soldiers without forming any triplet.
2. To allow extra soldiers from a profession (which might start forming groups), observe that if you want to keep the number of triplets in that profession (\lfloor x/3 \rfloor) below some value, the adversary can take extra blocks of 3 soldiers. In fact, for a given profession, the maximum number of soldiers that can be taken without reaching an extra group (using a "group slot") is bounded by (3(r+1)-1) if you allow (r) groups from that profession.
3. Let the base picks be (\sum_{\text{profession}} \min(T,2)). For each profession with (T > 2), create a list of potential gains (in blocks) as follows. Define (d = \lceil (T-2)/3 \rceil). For the first (d-1) extra group slots the gain is 3 per slot, and the last slot gives a gain of (T - 2 - 3,(d-1)) (which is between 1 and 3). Then, if the adversary is allowed a total of (k-1) extra group slots across all professions, the maximum number of soldiers that can be selected without forcing (k) groups is: [ \text{MAX} = \Bigl( \sum_{\text{profession}} \min(T,2) \Bigr) + \text{(sum of the top }k-1 \text{ gains over all professions)}. ] Thus, the answer is (\text{MAX} + 1). (If selecting all soldiers still yields less than (k) groups, output -1.)

inputFormat

The input begins with two integers (n) and (k) ((1 \leq n \leq 10^5,\ 1 \leq k \leq 10^9)), representing the number of squads and the number of pure professional groups to form. Each of the next (n) lines contains two integers (a_i) and (b_i) ((1 \leq a_i \leq 10^9,\ 1 \leq b_i \leq 10^9)), where (a_i) indicates the profession and (b_i) the number of soldiers in the (i)th squad.

Note that soldiers with the same profession (i.e. same (a_i)) are indistinguishable and their counts should be summed.

outputFormat

Print a single integer: the minimum number of soldiers that must be chosen to guarantee that it is possible to form at least (k) pure professional groups. If it is impossible to form (k) groups from all the available soldiers, print -1.

sample

1 1
1 5

3