Description

There are $n$ groups of parcels waiting to be delivered. There are $c_i$ parcels in the $i$-th group, where each parcel has the same weight of $w_i$ ($w_i$ is either $1$ or $2$) and should be delivered to the $f_i$-th floor.

There is an elevator which can carry parcels with a maximum total weight of $k$ ($k$ is even) for each ride. The elevator will start from the ground floor and move gradually towards the hightest floor $h$ where a parcel in the elevator should be delivered and finally move back to the ground floor, costing $h$ units of electric power for that ride.

More formally, let $(w, f)$ be a parcel whose weight is $w$ and should be delivered to the $f$-th floor. A multiset (a set which allows duplicated elements) of parcels $\mathbb{P}$ can be delivered in the same ride if $\sum\limits_{(w, f) \in \mathbb{P}} w \le k$. This ride will cost $\max\limits_{(w, f) \in \mathbb{P}} f$ units of electric power.

What's the minimum total units of electric power needed to deliver all parcels?

Note that each ride can contain parcels from different groups and each group of parcels can be delivered through multiple rides. You can treat this problem as if there are a total of $\sum\limits_{i=1}^n c_i$ parcels to be delivered, just that some parcels may have the same weight and the same destination.

Input Format

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $k$ ($1 \le n \le 10^5$, $2 \le k \le 2 \times 10^{10}$, $k$ is even) indicating the number of groups and the capacity of the elevator.

For the following $n$ lines, the $i$-th line contains three integers $c_i$, $w_i$ and $f_i$ ($1 \le c_i \le 10^5$, $w_i \in \{1, 2\}$, $1 \le f_i \le 10^5$) indicating the number of parcels in the $i$-th group, the weight of each parcel and the destination of the parcels.

It's guaranteed that the sum of $n$ over all test cases does not exceed $3 \times 10^5$.

Output Format

For each test case output one line containing one integer indicating the minimum total units of electric power needed to deliver all parcels.

2
4 6
1 1 8
7 2 5
1 1 7
3 2 6
8 1200000
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345

24
100000

Hint

For the first sample test case we can follow this strategy:

• In the first ride, deliver parcel $(2, 6)$, $(2, 6)$ and $(2, 5)$. This ride costs $6$ units of electric power.
• In the second ride, deliver parcel $(1, 8)$, $(1, 7)$, $(2, 6)$ and $(2, 5)$. This ride costs $8$ units of electric power.
• In the third ride, deliver parcel $(2, 5)$, $(2, 5)$ and $(2, 5)$. This ride costs $5$ units of electric power.
• In the fourth ride, deliver parcel $(2, 5)$ and $(2, 5)$. This ride costs $5$ units of electric power.

The total units of electric power is $6 + 8 + 5 + 5 = 24$. It can be proven that this is the minimum total units of electric power needed.

For the second sample test case, all parcels can be delivered in the same ride.