Ke1vin is a smart but crazy high school student. He usually bets with his good friend, dreamoon about the grades at school. One day, he said: "Getting 100 in all subjects is just too easy, so this time let's bet something special.
You specify a target score, and I will make my average score in midterm exam as you specify! Let's bet it for a week of food!".
Stupid dreamoon think it's impossible for ke1vin to do that. So he quickly agree to him. But in fact, ke1vin has a strong skill. He can control his score in range [Li,Ri] for subject Si(necessarily integer!).
There are N subjects in this midterm. Now given the target B dreamoon specified and all the weight wi for Subject Si. Please calculate the minimum difference between B and the average score ke1vin can control.
Remeber, the score of each subject MUST be integer!
The input contains an integer T in the first line, denoting the number of test cases.
Each test case starts with two integer B, N, and then following N lines. The i'th line contains three integer Li, Ri, wi.
1 <= N <= 50
for any i, 0<=Li<=Ri<=100, 1 <= wi <= 50
For each test case, you should print a line containing a fraction in lowest term(that is, the fraction q/p you print should have the property gcd(p,q) = 1).
3 0 3 100 100 1 100 100 2 100 100 3 99 2 90 100 2 90 100 3 95 2 94 94 5 100 100 1
100/1 0/1 0/1
Migrated from old NTUJ.
dreamoon
| No. | Testdata Range | Score |
|---|