Professor Yzal does not like to grade the exams of his students, so that he assigns this task to his assistants. Final students’ grades are defined as weighted sums of the grades obtained in the exams. But Professor Yzal does not define a priori the exam’s relative weights. Instead of that, only when the assistants end their job (and all the students’ grades in each exam are known) Professor Yzal decides the exam’s weights. He does it trying to be pleasant with the whole class, so that the assigned weights should maximize the average final grade that the class obtains, and expecting that eventual complaints about his grading criteria will be as few as possible. And finally, maybe rewarding harder exams, Yzal defines that the weight of every particular exam should lie within a specific range of values. This term is about to finish and you were hired to help Yzal with his lazy grading job. Your task is to write a program that, given the students’ grades and the reasonable range of weights for each exam, determines the maximum possible average according to the following rules: • Each exam must have a weight, defined as an integer number in the closed interval [0,100], describing the assigned percentage. • The weight of an exam i must be in an integer closed interval [mini,maxi] that describes the corresponding reasonable range previously defined by Yzal. • The sum of all exam weights must be 100. • The final grade of each student is a weighted sum calculated as the sum of his/her own grades previously multiplied by the corresponding exam weight divided by 100. • The exam weights are so chosen that the average of the students’ final grades is maximized. Input There are several cases to consider. Each test case is described as follows: • A line with two integer numbers S and N, separated by a blank, (1 ≤ S ≤ 100, 1 ≤ N ≤ 20), where S corresponds to the number of students and N corresponds to the number of exams in the course. • Each one of the following S lines describes the grades of each student, containing N integer numbers cj1,cj2,...,cjN, separated by a blank, (0 ≤ cji ≤ 100 for each 1 ≤ i ≤ N), where cji indicates the grade obtained by the student j in the exam i (1 ≤ j ≤ S, 1 ≤ i ≤ N). • Each one of the following N lines describes the reasonable range of weights of each exam, con- taining two integer numbers mini, maxi, separated by a blank (0 ≤ mini ≤ maxi ≤ 100), where mini and maxi represent the minimum and maximum weight that can be assigned to the exam i, respectively (1 ≤ i ≤ N). You can suppose that ∑N ∑N mini ≤ 100, The last test case is followed by a line containing two zeros. i=1 i=1 and maxi ≥ 100.
2/2 Output For each given case, output a single line with a number indicating the maximum possible average of the students’ final grades if the weights are defined according to the rules. The answer should be formatted and approximated to two decimal places. The floating point delimiter must be ‘.’ (i.e., the dot). The rounding applies towards the nearest neighbor unless both neighbors are equidistant, in which case the result is rounded up (e.g., 78.312 is rounded to 78.31; 78.566 is rounded to 78.57; 78.345 is rounded to 78.35, etc.). Sample Input 11 0 0 100 22 50 90 70 50 0 100 0 100 22 50 90 70 50 30 70 30 70 22 50 90 70 50 50 50 50 50 22 73 52 92 81 20 50 60 80 00 Sample Output 0.00 70.00 67.00 65.00 72.90