Minimize Total Race Time

Drip is preparing for the WDC and has n sets of tires. He must complete m laps. When using the i-th set of tires, the time required to finish its j-th lap (for that set) is given by\(a_i + b_i (j-1)^2\) seconds.

Whenever Drip switches to a new set of tires (i.e. enters the pit stop) his car loses an extra t seconds. Note that the first set of tires does not require a pit stop.

Your task is to choose an order in which to use some (or all) of these tire sets and decide how many consecutive laps to run on each so that the total race time is minimized. The total time is the sum of the lap times on each set plus a pit‐stop cost of t seconds for every tire change (i.e. for every set used after the first).

For a given tire set \(i\) used continuously for \(k\) laps, the time spent is:

\[ T(i,k)=\sum_{j=1}^{k} \Bigl(a_i+b_i (j-1)^2\Bigr)= k\,a_i + b_i\cdot \frac{(k-1)\,k\,(2k-1)}{6}. \]

You are given the parameters a_i and b_i for each tire set. It is not allowed to use the same tire set more than once. Determine the minimum total time required to finish m laps.

inputFormat

The first line contains three integers:
    n (the number of tire sets), m (the total laps) and t (the pit stop time in seconds).

The following n lines each contain two integers a_i and b_i, representing the base lap time and the coefficient for the squared term respectively for the i-th tire set.

outputFormat

Output a single integer, which is the minimum total time (in seconds) required to complete m laps.

sample

2 3 5
1 1
2 2

8

</p>