Chef is Travelling
All submissions for this problem are available.
Chef is the king of a Country and conquered other country and wants to travel them.During that he plans to visit n cities.For city i ai is the maximum number of gift packs that an tourist is allowed to bring to the city, and bi is the number of citizens in the city.
The Smart chef is going to bring some presents to the city he will be visiting. The presents are packed in gift packs, x presents in each. The chef will take to his chopper exactly a1+...+an gift packs.
As the chef goes in the ith city, he takes ai gift packs and goes out. On the first day in the city the chef gets to know the citizens. On the second and all subsequent days the chef gives presents to the citizens — each of the bi citizens gets one present per day. The chef leaves the city in the evening of the day when the number of presents left is strictly less than the number of citizens. He throws away the remaining presents.
The Chef will spend exactly c days traveling. The time spent in chopper between the cities is considered to be negligible. In how many ways can one choose the positive integer x so that the planned event will take exactly c days?
The First line contains Single Integer T, the number of test cases.
The Second line contains space-separated integers n and c.
The next n lines contain pairs of space-separated integers ai,bi (1 ≤ i ≤ n) — the number of giftpacks he can bring to the i-th city and the number of citizens of the ith city.
Print a single number k — the number of ways to choose x so as to travel for exactly c days. If there are infinitely many possible values of x, print -1.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 10000
- 1 ≤ ai , bi , c ≤ 109
Subtask #1 : (10 points)
Subtask #2 : (90 points)
In the example there is only one suitable value x = 5.
Then the chef takes 1 gift pack with 5 presents to the first city.
Here he spends 2 days: he hangs around on the first day, and he gives away five presents on the second day.
He takes 2 suitcases with 10 presents to the second city.Here he spends 3 days — he gives away 4 presents on the second and the third days and throws the remaining 2 presents . In total, the chef spends 5 days traveling.
For x = 4 or less the chef won't have enough presents for the second day in the first city, so the journey will end too soon. For x = 6 and more the chef will spend at least one more day in the second city, and the journey will take too long.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions