题目描述

午高峰的外卖站点里，骑手小蓝正紧盯着屏幕上待处理的 $N$ 个订单。这些订单必须严格按照系统列表中的固定顺序依次配送，不可打乱或跳过。为了顺利完成任务，小蓝计划将这 $N$ 个订单分成若干个批次进行配送。

站点内停放着 $M$ 种不同的交通工具，每种工具都具备两个属性：平均路途耗时 $A_i$ 和箱体拥挤系数 $B_i$。对于每一个批次，小蓝可以根据该批次订单的数量，从 $M$ 种工具中独立选择一种最合适的。

假设某一个批次包含 $L$ 个订单，且小蓝选用第 $i$ 种交通工具，则该批次的总耗时由以下三部分组成：

1. 路途耗时：$L \times A_i$ 秒。
2. 取餐耗时：由于箱内挤压，整理 $L$ 个订单需处理 $\frac{L(L-1)}{2}$ 对挤压关系，每对耗时 $B_i$，共计 $\frac{L(L-1)}{2} \times B_i$ 秒。
3. 折返耗时：分批配送存在额外的折返成本。处理第一个批次时，由于小蓝默认已在站点装车完毕可以直接出发，此项耗时为 $0$ 秒；但从第二个批次开始，每开启一个新的批次，都必须花费固定的 $X$ 秒用于返回站点装载下一批订单。

现在，请你帮助小蓝规划最优的分批方案，并计算出送完 $N$ 个订单所需的最小总耗时。

输入格式

一行包含三个整数 $N$、$M$ 和 $X$，分别表示订单总数、交通工具的种类数，以及固定耗时。

接下来的 $M$ 行，每行包含两个整数 $A_i$ 和 $B_i$，依次表示第 $i$ 种交通工具的平均路途耗时与箱体拥挤系数。

输出格式

输出一个整数，表示完成全部 $N$ 个订单配送任务所需的最小总耗时（单位：秒）。

5 2 40
10 8
2 20

118

提示

【样例说明】

一种最优的方案是分成 $2$ 批配送：

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \le N, M \le 100$；

对于所有评测用例，$1 \le N, M \le 5000$，$1 \le X, A_i, B_i \le 10^9$。