Fibonacci Bugs

Bug colonies have been the center of attention of scientists for a long time. Through some technological advancements, we are now able to describe a bug colony using a number known as the degree of the colony. A colony of degree $0$ represents a male bug and one of degree $1$ represents a female bug. A colony of degree $i > 1$ is obtained by merging a colony of degree $i - 1$ together with a colony of degree $i - 2$. As such, the first few colonies are as follows:

• Colony $0$: a male
• Colony $1$: a female
• Colony $2$: a male and a female
• Colony $3$: a male and two females

You are the owner of the biggest bug farm in the world, having at your disposal a virtually infinite amount of colonies of any degree. Each day you receive $N$ offers, each described by two numbers $A_i$ and $B_i$, meaning that you can sell as many colonies of type $A_i$ as you want and get $B_i$ money for each colony of that type.

Unfortunately, the antitrust laws on the bug trading market forbid you to sell more than $K$ bugs in a single day (selling a colony is equivalent to selling all the bugs in that colony).

Task

Given the description of $T$ days, if you optimally choose which offers to accept, what is the maximum amount of money you can obtain in each day?

Input data

The first line will contain the number of days $T$.

The first line of each day contains the number of bugs $N$ and the most bugs you can sell that day $K$. The next $N$ lines of each day contain the pair of numbers $A_i$ and $B_i$.

Output data

You will print $T$ lines, the $i^{th}$ one containing the answer for the $i^{th}$ day.

Constraints and clarifications

• $1 \leq T, N, K, A_i \leq 10^5$
• $\sum_{i=1}^{T}N_i \leq 10^5$
• $1 \leq B_i \leq 10^9$
• For tests worth 50 points: $1 \leq N, K \leq 5 \ 500$ and $1 \leq A_i \leq 11 \ 000$.

Example

stdin

1
5 11
1 2
2 2
3 5
4 9
5 50

stdout

56

Explanation

It is optimal to choose the $5^{th}$ offer once and the $1^{st}$ one $3$ times.