#include #include #include using namespace atcoder; using mint = modint1000000007; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 using ll = long long; struct F { ll a, b; F(ll a, ll b) : a(a), b(b) {} }; struct ConvexHullTrick { deque deq; bool check(F &f1, F &f2, F &f3) { return (f2.a - f1.a) * (f3.b - f2.b) >= (f2.b - f1.b) * (f3.a - f2.a); } ll f(F &f1, ll x) { return f1.a * x + f1.b; } public: // a_{prev} >= a void add_line(ll a, ll b) { F f1 = F(a, b); while(deq.size() >= 2 && check(deq[deq.size()-2], deq[deq.size()-1], f1)) { deq.pop_back(); } deq.push_back(f1); } // x_{prev} <= x ll query(ll x) { while(deq.size() >= 2 && f(deq[0], x) >= f(deq[1], x)) { deq.pop_front(); } return f(deq[0], x); } }; bool check(long long a0,long long b0,long long a1,long long b1,long long x,long long y){ return (a0-a1)*x < (b1-b0)*y; } int main(){ int n; cin>>n; vector> a(n); rep(i,n){ cin>>a[i].first>>a[i].second; swap(a[i].first,a[i].second); } sort(a.begin(),a.end()); ConvexHullTrick C; rep(i,n){ C.add_line(a[i].first,-a[i].second); } long long ans = 0; deque> D; rep(i,C.deq.size()){ D.emplace_back(C.deq[i].a,C.deq[i].b); } rep(i,n){ int l = 0,r = D.size()-1; while(r-l>3){ int m0 = l + (r-l)/3; int m1 = l + (r-l)/3 * 2; if(check(D[m0].first,D[m0].second,D[m1].first,D[m1].second,a[i].second,a[i].first))r = m1; else l = m0; } for(int j=l;j<=r;j++){ long long cur = 0; cur += D[j].second * a[i].first; cur += D[j].first * a[i].second; ans = min(ans,cur); } } cout<<-ans<