P8179 "EZEC-11" Tyres

This problem once had an interesting background story.

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.

The first line contains three integers $n, m, t$. The next $n$ lines each contain two integers $a_i, b_i$.

Output one integer, representing the minimum possible total time.

**[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