Problem Description

In the Lanqiao Kingdom, the king commands a powerful army made up of $n$ squads. Each squad consists of soldiers of the same profession. Specifically, the $i$-th squad contains $b_i$ soldiers whose profession is $a_i$.

Recently, the king plans to hold a grand military parade in the palace square to celebrate the kingdom’s prosperity. However, while the soldiers were entering, a sudden storm disrupted their formation, mixing soldiers from different squads together and completely messing up the order.

Although the king cannot know the exact profession of each individual soldier, to ensure the ceremony can proceed smoothly, the king plans to select some of these chaotic soldiers to form $k$ “pure-profession groups” for inspection. A “pure-profession group” is defined as a team of $3$ soldiers of the same profession.

Ask: what is the minimum number of soldiers the king must select to guarantee that these soldiers can form $k$ “pure-profession groups”?

Input Format

The first line contains an integer $T$, indicating that the input contains $T$ test cases.

The following describes the $T$ test cases in order.

For each test case, the first line contains two integers $n_t$ and $k$, separated by a space, representing the number of squads and the number of pure-profession groups to form.

The next $n_t$ lines each contain two integers $a_i$ and $b_i$, separated by a space, representing the profession and the number of soldiers in the $i$-th squad.

Output Format

Output $T$ lines. Each line contains one integer, representing the answer for each test case: the minimum number of soldiers the king must select to form $k$ “pure-profession groups”. If it is impossible to form $k$ “pure-profession groups” no matter what, output $-1$.

2
3 2
1 3
2 3
3 3
3 5
1 3
2 3
3 3

8
-1

Hint

For $50\%$ of the test cases, $1 \le T \le 10$, $1 \le \sum_{t=1}^T n_t \le 2 \times 10^3$, $1 \le a_i, b_i \le 10^5$, $1 \le k \le 10^7$.

For all test cases, $1 \le T \le 100$, $1 \le \sum_{t=1}^T n_t \le 2 \times 10^5$, $1 \le a_i, b_i \le 10^9$, $1 \le k \le 10^{13}$.

Sample Explanation

In the first sample, to form $2$ “pure-profession groups”, the king must select at least $8$ soldiers. If only $7$ soldiers are selected, then the professions of these $7$ soldiers could be $1, 1, 1, 2, 2, 3, 3$, making it impossible to form $2$ “pure-profession groups”.

In the second sample, even if all soldiers are selected, it is still impossible to form $5$ “pure-profession groups”, so output $-1$.

Translated by ChatGPT 5