「EZEC-11」Tyres

这道题曾经有有趣的题目背景。

有 $n$ 套轮胎，滴叉需要用这些轮胎跑 $m$ 圈。 使用第 $i$ 套轮胎跑的第 $j$ 圈（对每套轮胎单独计数）需要 $a_i+b_i(j-1)^2$ 秒。在本题中，你不需要担心爆胎，安全车，红旗或者不同的比赛策略。 滴叉需要进入维修站来更换轮胎，所消耗的时间为 $t$ 秒。特别地，滴叉使用的**第一套**轮胎不需要进站更换。 为了帮助滴叉拿下 WDC，你需要最小化总时间，总时间等于每圈的时间之和加上进站所花费的时间。

第一行输入三个整数 $n,m,t$。 接下来 $n$ 行，每行输入两个整数 $a_i,b_i$。

输出一个整数，代表总时间的最小值。

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

**【样例解释】** 对于第一个样例： * 你先让滴叉用第一套轮胎跑一圈，消耗 $10$ 秒。 * 然后进站更换第二套轮胎，消耗 $50$ 秒。 * 然后用第二套轮胎跑三圈。第一圈消耗 $100$ 秒，第二圈消耗 $100+1\times 1^2=101$ 秒，第三圈消耗 $100+1\times 2^2=104$ 秒。 * 总时间为 $10+50+100+101+104=365$ 秒。 对于第二个样例，滴叉每圈更换一次新轮胎。 注意一套轮胎被卸下后并不会重置它跑的圈数。 对于第三个样例，滴叉先使用第一套轮胎跑 $4$ 圈，然后更换第二套轮胎跑 $6$ 圈。 **【数据范围】** **本题采用捆绑测试**。 - Subtask 1（7 pts）：$n=1$。 - Subtask 2（9 pts）：$n\leq10$，$m\leq 100$。 - Subtask 3（13 pts）：$t=0$。 - Subtask 4（21 pts）：保证 $a_i,b_i$ 随机生成。 - Subtask 5（50 pts）：无特殊限制。 对于前 $100\%$ 的数据，$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$。