为简便，以下 $(w,l)\rightarrow(x,y)$。

首先如果 $(x_1,y_1)$ 与 $(x_2,y_2)$ 满足 $x_1\le x_2,y_1\le y_2$，则 $(x_1,y_1)$ 与 $(x_2,y_2)$ 合购更优，因此忽略这样的 $(x_1,y_1)$。

于是直接考虑剩下的 $(x_2,y_2)$ 会构成怎样的平面上的点集。

显然 $x$ 单调增时 $y$ 单调减。

这个东西可以拿个单调栈求出。

剩下的点按 $x$ 升序排列。

然后可以发现剩下的分组必然各自得是连续的一段，否则不优。

设 $f_n$ 表示第 $n$ 个点是某个分组的结尾时的最小花费。

稳妥妥的斜率优化。

直接做就好了。

说起来这个是否满足四边形不等式（交叉小于包含）啊？

p.s. 用排序不等式可证。

所以也可以半在线的决策单调性优化 dp。

但我不会。

Code

#include <algorithm>
#include <deque>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    // freopen("QAQ.out","w",stdout);
#endif
    typedef std::pair<uint,uint>Pair;
    typedef std::pair<ullt,ullt>Pair2;
    uint n;scanf("%u",&n);std::vector<Pair>V(n);
    for(auto&v:V)scanf("%u%u",&v.first,&v.second);
    std::sort(V.begin(),V.end());
    {
        std::vector<Pair>Keep;
        for(auto v:V)
        {
            while(Keep.size()&&Keep.back().second<=v.second)Keep.pop_back();
            Keep.push_back(v);
        }
        V=Keep;
    }
    {
        std::deque<Pair2>Keep;
        auto val=[](Pair2 p,ullt x){return p.first*x+p.second;};
        ullt ans=0;
        for(auto v:V)
        {
            Pair2 line(v.second,ans);
            while(Keep.size()>=2)
            {
                Pair2 line1=Keep.back(),line2=Keep[Keep.size()-2];
                if((line.second-line2.second)*(line2.first-line1.first)<=
                    (line1.second-line2.second)*(line2.first-line.first))
                    Keep.pop_back();
                else break;
            }
            Keep.push_back(line);
            while(Keep.size()>1&&val(Keep[0],v.first)>=val(Keep[1],v.first))Keep.pop_front();
            ans=val(Keep[0],v.first);
        }
        printf("%llu\n",ans);
    }
    return 0;
}