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: interview

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