Write The Contest

Polycarp, Arkady's friend, prepares to the programming competition and decides to write a contest. The contest consists of n problems and lasts for T minutes. Each of the problems is defined by two positive integers a_i and p_i — its difficulty and the score awarded by its solution.

Polycarp's experience suggests that his skill level is defined with positive real value s, and initially s=1.0. To solve the i-th problem Polycarp needs a_i/s minutes.

Polycarp loves to watch series, and before solving each of the problems he will definitely watch one episode. After Polycarp watches an episode, his skill decreases by 10%, that is skill level s decreases to 0.9s. Each episode takes exactly 10 minutes to watch. When Polycarp decides to solve some problem, he firstly has to watch one episode, and only then he starts solving the problem without breaks for a_i/s minutes, where s is his current skill level. In calculation of a_i/s no rounding is performed, only division of integer value a_i by real value s happens.

Also, Polycarp can train for some time. If he trains for t minutes, he increases his skill by C ⋅ t, where C is some given positive real constant. Polycarp can train only before solving any problem (and before watching series). Duration of the training can be arbitrary real value.

Polycarp is interested: what is the largest score he can get in the contest? It is allowed to solve problems in any order, while training is only allowed before solving the first problem.

Input

The first line contains one integer tc (1 ≤ tc ≤ 20) — the number of test cases. Then tc test cases follow.

The first line of each test contains one integer n (1 ≤ n ≤ 100) — the number of problems in the contest.

The second line of the test contains two real values C, T (0 < C < 10, 0 ≤ T ≤ 2 ⋅ 10^5), where C defines the efficiency of the training and T is the duration of the contest in minutes. Value C, T are given exactly with three digits after the decimal point.

Each of the next n lines of the test contain characteristics of the corresponding problem: two integers a_i, p_i (1 ≤ a_i ≤ 10^4, 1 ≤ p_i ≤ 10) — the difficulty and the score of the problem.

It is guaranteed that the value of T is such that changing it by the 0.001 in any direction will not change the test answer.

Please note that in hacks you can only use tc = 1.

Output

Print tc integers — the maximum possible score in each test case.

Examples

Input

2 4 1.000 31.000 12 3 20 6 30 1 5 1 3 1.000 30.000 1 10 10 10 20 8

Output

7 20

Note

In the first example, Polycarp can get score of 7 as follows:

1. Firstly he trains for 4 minutes, increasing s to the value of 5;
2. Then he decides to solve 4-th problem: he watches one episode in 10 minutes, his skill level decreases to s=5*0.9=4.5 and then he solves the problem in 5/s=5/4.5, which is roughly 1.111 minutes;
3. Finally, he decides to solve 2-nd problem: he watches one episode in 10 minutes, his skill level decreases to s=4.5*0.9=4.05 and then he solves the problem in 20/s=20/4.05, which is roughly 4.938 minutes.

This way, Polycarp uses roughly 4+10+1.111+10+4.938=30.049 minutes, to get score of 7 points. It is not possible to achieve larger score in 31 minutes.

In the second example, Polycarp can get 20 points as follows:

1. Firstly he trains for 4 minutes, increasing s to the value of 5;
2. Then he decides to solve 1-st problem: he watches one episode in 10 minutes, his skill decreases to s=5*0.9=4.5 and then he solves problem in 1/s=1/4.5, which is roughly 0.222 minutes.
3. Finally, he decides to solve 2-nd problem: he watches one episode in 10 minutes, his skill decreases to s=4.5*0.9=4.05 and then he solves the problem in 10/s=10/4.05, which is roughly 2.469 minutes.

This way, Polycarp gets score of 20 in 4+10+0.222+10+2.469=26.691 minutes. It is not possible to achieve larger score in 30 minutes.

inputFormat

Input

The first line contains one integer tc (1 ≤ tc ≤ 20) — the number of test cases. Then tc test cases follow.

The first line of each test contains one integer n (1 ≤ n ≤ 100) — the number of problems in the contest.

The second line of the test contains two real values C, T (0 < C < 10, 0 ≤ T ≤ 2 ⋅ 10^5), where C defines the efficiency of the training and T is the duration of the contest in minutes. Value C, T are given exactly with three digits after the decimal point.

Each of the next n lines of the test contain characteristics of the corresponding problem: two integers a_i, p_i (1 ≤ a_i ≤ 10^4, 1 ≤ p_i ≤ 10) — the difficulty and the score of the problem.

It is guaranteed that the value of T is such that changing it by the 0.001 in any direction will not change the test answer.

Please note that in hacks you can only use tc = 1.

outputFormat

Output

Print tc integers — the maximum possible score in each test case.

Examples

Input

2 4 1.000 31.000 12 3 20 6 30 1 5 1 3 1.000 30.000 1 10 10 10 20 8

Output

7 20

Note

In the first example, Polycarp can get score of 7 as follows:

1. Firstly he trains for 4 minutes, increasing s to the value of 5;
2. Then he decides to solve 4-th problem: he watches one episode in 10 minutes, his skill level decreases to s=5*0.9=4.5 and then he solves the problem in 5/s=5/4.5, which is roughly 1.111 minutes;
3. Finally, he decides to solve 2-nd problem: he watches one episode in 10 minutes, his skill level decreases to s=4.5*0.9=4.05 and then he solves the problem in 20/s=20/4.05, which is roughly 4.938 minutes.

This way, Polycarp uses roughly 4+10+1.111+10+4.938=30.049 minutes, to get score of 7 points. It is not possible to achieve larger score in 31 minutes.

In the second example, Polycarp can get 20 points as follows:

1. Firstly he trains for 4 minutes, increasing s to the value of 5;
2. Then he decides to solve 1-st problem: he watches one episode in 10 minutes, his skill decreases to s=5*0.9=4.5 and then he solves problem in 1/s=1/4.5, which is roughly 0.222 minutes.
3. Finally, he decides to solve 2-nd problem: he watches one episode in 10 minutes, his skill decreases to s=4.5*0.9=4.05 and then he solves the problem in 10/s=10/4.05, which is roughly 2.469 minutes.

This way, Polycarp gets score of 20 in 4+10+0.222+10+2.469=26.691 minutes. It is not possible to achieve larger score in 30 minutes.

样例

2
4
1.000 31.000
12 3
20 6
30 1
5 1
3
1.000 30.000
1 10
10 10
20 8

7
20

</p>