题目背景

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

题目描述

有 $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$。