Background

This problem once had an interesting background story.

Problem Description

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

For the $i$-th set of tyres, the time needed for its $j$-th lap (counted separately for each set of tyres) is $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 race strategies.

Di Cha needs to enter the pit to change tyres, which takes $t$ seconds. In particular, the first set of tyres Di Cha uses does not require a pit stop to change.

To help Di Cha win the WDC, you need to minimize the total time. The total time equals the sum of lap times plus the time spent on pit stops.

Input Format

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

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

Output Format

Output one integer, representing the minimum possible total time.

2 4 50
10 100
100 1

365

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

598

3 10 30
1000 8
1050 3
1100 1

10607

Hint

[Sample Explanation]

For the first sample:

• First, you let Di Cha run one lap with the first set of tyres, costing $10$ seconds.
• Then pit to change to the second set of tyres, costing $50$ seconds.
• Then use the second set of tyres to run three laps. The first lap costs $100$ seconds, the second lap costs $100 + 1 \times 1^2 = 101$ seconds, and the third lap costs $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 to a new set of tyres every lap.

Note that after a set of tyres is removed, its lap count will not be reset.

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

[Constraints]

This problem uses bundled testdata.

• 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): It is guaranteed that $a_i, b_i$ are generated randomly.
• Subtask 5 (50 pts): No special constraints.

For all testdata, $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$.

Translated by ChatGPT 5