This year at the Olympics a new event was introduced: the mixed distance relay race. In this event, all of the athletes from each delegation try to run a $$$D$$$ meter race as fast as possible. Compared to the traditional competitions, there is one key difference: each team decides how to split the total distance among all of its runners.

The rules are:

• The athletes must run a total distance of $$$D$$$ meters.
• Each athlete starts running as soon as the previous teammate finishes his split.
• Each athlete must run an integer amount of meters.
• Each athlete must run at least 1 meter.
• The delegation's time is the sum of all individual runners' times.

As the chief strategist of your country's delegation, you must come up with a way of splitting the distance such that the total time is as small as possible.

You know that your delegation is composed of $$$N$$$ runners. Each one of them is characterized by two numbers: an initial speed, $$$a_i$$$, and a slowing down rate, $$$b_i$$$.

Initially, runner $$$k$$$ can advance a meter in $$$a_k$$$ seconds and, after that, each subsequent meter takes $$$b_k$$$ more seconds than the previous one. To be precise, the time it takes for athlete $$$k$$$ to run the $$$j^{th}$$$ meter is $$$a_k + b_k * (j - 1)$$$.

Knowing all the details about your delegation, you are asked to compute the smallest amount of time you could obtain with a valid way of splitting the distance among your athletes.