题目描述

n 个人一起排队接水，第$i$个人的重要性是$a[i]$，需要$b[i]$的时间来接水（$1 \le n \le 100000$，$1 \le a[i] \le 1000$, $1 \le b[i] \le 1000$ ）。同时只能有一个人接水，正在接水的人和没有接水的人都需要等待。完成接水的人会立刻消失，不会继续等待。令第$i$个人的等待时间为$t[i]$, 其不高兴值定义为：$c[i]=a[i]*t[i]$。你可以决定所有人接水的顺序，并希望最小化所有人不高兴值之和。

输入格式

第一行两个正整数 $n$。 接下来$n$行，每行两个整数，表示$a[i]$和$b[i]$。

输出格式

一行，一个整数表示所有人不高兴值之和的最小值。

样例1

输入

4
3 5
1 2
4 1
2 4

输出

25

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 1\times10^5, 1 \le a[i],b[i] \le1000$。