题目描述

凤爪最近迷上了大肥鱼（Fatseek）。写代码、查资料、想文案，他都要找大肥鱼聊上几句。

然而，和大肥鱼聊天需要消耗 token。为了让接下来的聊天计划顺利进行，凤爪决定提前规划 token 的购买方案。

凤爪已经知道了未来 $n$ 天的价格和需求：在第 $i$ 天，每购买 $1$ 个 token 需要花费 $p_i$ 元，而他当天需要消耗 $a_i$ 个 token。

购买和使用 token 的规则如下：

• 开始时，凤爪没有任何 token。
• 每天，他可以先按照当天的价格购买任意非负整数个 token，再消耗当天所需的 $a_i$ 个 token。
• 没用完的 token 可以留到之后的任意一天使用，不会过期，也没有储存费用。
• 每天可购买的数量和账户可保留的 token 数量均没有上限。
• 每天的需求都必须在当天满足，不能推迟；已购买的 token 不能退款。

请你求出，满足这 $n$ 天全部需求所需的最少总花费。

输入格式

第一行包含一个整数 $n$，表示天数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $p_i,a_i$，分别表示第 $i$ 天每个 token 的价格和当天需要消耗的 token 数量。

输出格式

输出一个整数，表示最少总花费。

样例

5
5 2
3 4
6 1
2 3
4 2

35

1
1000000 1000000

1000000000000

样例说明

对于第一个样例，一种最优的购买方案如下：

• 第 $1$ 天，购买 $2$ 个 token，花费 $10$ 元，当天全部用完。
• 第 $2$ 天，购买 $5$ 个 token，花费 $15$ 元。当天使用 $4$ 个，剩余 $1$ 个留到第 $3$ 天使用。
• 第 $3$ 天，不购买 token，使用之前剩余的 $1$ 个。
• 第 $4$ 天，购买 $5$ 个 token，花费 $10$ 元。当天使用 $3$ 个，剩余 $2$ 个留到第 $5$ 天使用。
• 第 $5$ 天，不购买 token，使用之前剩余的 $2$ 个。

总花费为 $10+15+10=35$ 元，可以证明不存在花费更少的方案。

数据范围

对于所有测试数据，保证：

• $1\le n\le 10^5$；
• $1\le p_i,a_i\le 10^6$。

提示：答案可能超过 $32$ 位有符号整数的表示范围。