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 \cdot 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 \le tc \le 20$) — the number of test cases. Then $tc$ test cases follow.

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

The second line of the test contains two real values $C, T$ ($0 < C < 10$, $0 \le T \le 2 \cdot 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 \le a_i \le 10^4$, $1 \le p_i \le 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:  Firstly he trains for $4$ minutes, increasing $s$ to the value of $5$;  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;  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:  Firstly he trains for $4$ minutes, increasing $s$ to the value of $5$;  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.  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.

Difficulty: VERY_HARD
Tags: Dynamic programming

Sorting

Mathematics
Skill types: Dynamic programming

Sorting

Starter code:

Solutions:
from math import sqrt

class pro(object):

	def __init__(self, dif, sc):
		self.dif = dif
		self.sc = sc

	def __lt__(self, other):
		return self.dif > other.dif
T = int(input())
mul = [1]
for i in range(100):
	mul.append(mul[i] * 10 / 9)
inf = 1000000007
for t in range(T):
	n = int(input())
	(effi, tim) = list(map(float, input().split()))
	prob = []
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		prob.append(pro(x, y))
	prob.sort()
	f = [[inf for i in range(n + 1)] for j in range(1001)]
	f[0][0] = 0
	totsc = 0
	for i in range(n):
		totsc += prob[i].sc
		for j in range(totsc, prob[i].sc - 1, -1):
			for k in range(1, i + 2):
				f[j][k] = min(f[j][k], f[j - prob[i].sc][k - 1] + prob[i].dif * mul[k])
	for i in range(totsc, -1, -1):
		flag = False
		for j in range(n + 1):
			if sqrt(effi * f[i][j]) >= 1:
				res = 2 * sqrt(f[i][j] / effi) - 1 / effi + 10 * j
			else:
				res = f[i][j] + 10 * j
			if res <= tim:
				print(i)
				flag = True
				break
		if flag == True:
			break