具体就是把转移化成：$f_j=f_i-a_{j+1}b_i$。

然后将 $-a_{j+1}$ 当成横坐标，$f_j$ 当作纵坐标。维护一个下凸包。

因为 $-a_i$ 递增，所以一开始不把 $0$ 入队，防止破坏单调性。所以加了个初始化 $f_i=a_1b_i$。

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define X(p) (-b[p + 1]._a)
#define Y(p) (f[p])
const int N = 1e5 + 5;
int n, _n, f[N], q[N], l, r;
struct node{int _a, _b;} a[N], b[N];

inline bool cmp(node A, node B) {return (A._a == B._a) ? (A._b > B._b) : (A._a > B._a);}
inline bool check(int a, int b, int c, int d, bool f){
	if(f == 0) return (1.0 * a / b) <= (1.0 * c / d);
	return (1.0 * a / b) >= (1.0 * c / d);
} 
signed main(){
	cin >> n;
	for(int i = 1; i <= n; ++i) scanf("%lld%lld", &a[i]._a, &a[i]._b);
	sort(a + 1, a + 1 + n, cmp);
	for(int i = 1; i <= n; ++i) if(a[i]._b > b[_n]._b) b[++_n] = a[i];
	l = 1, r = 0;
	for(int i = 1; i <= n; ++i){
		while(l < r && check(Y(q[l]) - Y(q[l + 1]), X(q[l]) - X(q[l + 1]), b[i]._b, 1, 0)) ++l;
		f[i] = b[1]._a * b[i]._b;
		if(l <= r) f[i] = min(f[i], f[q[l]] + b[q[l] + 1]._a * b[i]._b);
		while(l < r && check(Y(q[r]) - Y(q[r - 1]), X(q[r]) - X(q[r - 1]), Y(i) - Y(q[r]), X(i) - X(q[r]), 1)) --r;
		q[++r] = i;
	}
	cout << f[n];
	return 0;
}