题目描述

小t是个狂热的F1赛车迷，他对F1赛车的特制轮胎也很感兴趣。于是，他想出了这样一个问题。 给你$n$种轮胎，每种轮胎都有一对特殊的属性：{$x$，$y$}，这种属性只会在一种情况下产生作用，如果这种轮胎被连续使用，第 $t$ 圈需要耗时 $x \\* y^{(t-1)}$ 秒 比方说，对于某一种轮胎，如果 $x = 3$ 且 $y = 2$ ，且一直使用这种类型的同一条轮胎，那么该轮胎完成第 $1$ 圈赛道耗时 $3$ 秒，完成第 $2$ 圈耗时 $3 * 2 = 6$ 秒，完成第 $3$ 圈耗时 $3 \\* 2^2 = 12$ 秒，依次类推。 同时给你一个整数 $a$ 和一个整数 $b$ 。 比赛总共包含 $a$ 圈，你可以选择 任意 一种轮胎开始比赛。每一种轮胎都有 无数条 。每一圈后，你可以选择耗费 $b$ 秒 换成 任意一种轮胎（也可以换成当前种类的新轮胎）。 小t想知道完成比赛所用的最少时间，聪明的你能告诉他吗？

输入格式

第一行有三个整数，分别为$n$，$a$，$b$，表示轮胎的种类数量，圈的数量和更换轮胎的时间。 接下来$n$行，每行两个数字，分别表示每一种轮胎的特有属性$x$，$y$。 $1\\leq n,x,b\\leq 10^5$ $1\\leq a \\leq 10^3$ $2\\leq y \\leq 10^5$

输出格式

一个数字，表示答案。

样例

2 4 5 
2 3 
3 4 

21

3 5 6 
1 10 
2 2 
3 4

25

提示

对于第一个样例： 第 1 圈：使用轮胎 $0$ ，耗时 $2$ 秒。 第 2 圈：继续使用轮胎 $0$ ，耗时 $2 \\* 3 = 6$ 秒。 第 3 圈：耗费 $5$ 秒换一条新的轮胎 $0$ ，然后耗时 2 秒完成这一圈。 第 4 圈：继续使用轮胎 $0$ ，耗时 $2 \\* 3 = 6$ 秒。 总耗时 $= 2 + 6 + 5 + 2 + 6 = 21$ 秒。 完成比赛的最少时间为 $21$ 秒。

by 励翔 2022春第二次排位赛