Bob has been provided with K containers each containing some distinct balls.It is given that container I contains balls numbered is to fi both inclusive. In order to get some balls out Bob has to open the container and take some or all the balls out of that container. The cost of the opening container i is ai and the cost of each ball that is to be taken out is bi. You have been asked to out N distinct balls from these containers numbered 1 to N. Your task is to achieve this using the minimum cost. Note:
• You are already aware that the balls numbered i, even if available in distinct containers are identical.
• All the containers are initially closed.
Input Format
The first line contains an integer, N, denoting the number of balls.
The next line contains an integer, K, denoting the number of containers.
Each line i of the K subsequent lines (where 0<=i<=K) contains an integer describing li. Each line i of the K subsequent lines (where 0 <=i 40.4,5 from 3rd container:(1+1*2)=>3.6,7,8,9,10 from 2rd:(20+5*10)=>70 .So the optimals answer is 113