407710: GYM102878 L Long Long Wanna Buy

Long Long wanna buy a new computer. Long Long thought he was a master, so he decided to buy accessories and assemble his own computer. But actually Long Long is a rookie, so he only cares about the price and service life of accessories. There are $$$N$$$ kinds of accessory and $$$M$$$ accessories for each kind. To assemble a computer, you need all the kinds of accessory and each kind only need one. When any one of the accessories reaches the service life, the computer is damaged. Long Long defines the price pre unite time of his computer is the total price he spent divided by the life of the computer. Now we will give you all the accessories, and you need to assemble a computer that the price pre unite time is the lowest.

The first line contains two integers $$$N,M(1\leq N,M \leq 1000)$$$ , which means the number of accessory kinds and the accessories number in each kind. The next $$$N$$$ line(s) contain $$$2 \times M$$$ numbers, $$$S_1,P_1,S_2,P_2...S_M,P_M (1 \leq S_i \leq S_i+1 \leq 1000,1 \leq P_i \leq 1000000)$$$ , $$$S_i$$$ means the i-th accessory service time, and $$$P_i$$$ means the price.

Please print only one number, which means the total price of your computer. If there is more than one combination make the price pre unite time is lowest, print the minimum total price.

3 3
1 2 2 2 3 5
3 5 6 2 7 8
2 4 3 4 3 5

11