Problem Description

There are $n$ sets of tires, and Di Cha needs to use these tires to complete $m$ laps.

Using the $i$-th set of tires for the $j$-th lap (counting laps separately for each set of tires) requires $a_i + b_i(j-1)^2$ seconds. In this problem, you do not need to worry about blowouts, safety cars, red flags, or different racing strategies.

Di Cha needs to enter the pit stop to change tires, which takes $t$ seconds. Specifically, the first set of tires used by Di Cha does not require a pit stop.

To help Di Cha secure the WDC, you need to minimize the total time, which is the sum of the time for each lap plus the time spent in the pit stop.

Input Format

The first line of input contains three integers $n, m, t$.

The next $n$ lines each contain two integers $a_i, b_i$.

Output Format

Output a single integer, representing the minimum total time.

Sample Input and Output

Sample Input #1

2 4 50
10 100
100 1

Sample Output #1

365

Sample Input #2

6 6 10
90 200
90 200
90 200
92 200
92 200
94 200

Sample Output #2

598

Sample Input #3

3 10 30
1000 8
1050 3
1100 1

Sample Output #3

10607

Notes

[Sample Explanation]

For the first sample:

• Di Cha first uses the first set of tires for one lap, which takes $10$ seconds.
• Then enters the pit stop to change to the second set of tires, taking $50$ seconds.
• Then uses the second set of tires for three laps. The first lap takes $100$ seconds, the second lap takes $100 + 1 \times 1^2 = 101$ seconds, and the third lap takes $100 + 1 \times 2^2 = 104$ seconds.
• The total time is $10 + 50 + 100 + 101 + 104 = 365$ seconds.

For the second sample, Di Cha changes a new set of tires every lap.

Note that the number of laps a set of tires has run does not reset when it is removed.

For the third sample, Di Cha first uses the first set of tires for $4$ laps, then changes to the second set of tires for $6$ laps.

[Data Range]

This problem uses batched testing.

• Subtask 1 (7 pts): $n = 1$.
• Subtask 2 (9 pts): $n \leq 10$, $m \leq 100$.
• Subtask 3 (13 pts): $t = 0$.
• Subtask 4 (21 pts): $a_i, b_i$ are generated randomly.
• Subtask 5 (50 pts): No special restrictions.

For $100\%$ of the data, $1 \leq n, b_i \leq 500$, $0 \leq t \leq 500$, $1 \leq m \leq 2 \times 10^5$, $1 \leq a_i \leq 10^9$.

见题面 Input 部分

见题面 Output 部分