分析

发现题面就是要我们求这个东西 。这个显然显然单次枚举是 。我们考虑我们维护了一个上凸壳。所以我们只需要找到凸壳的顶点就好了，而考虑到是凸壳，那么考虑三分法解决。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
#define LL long long
const LL inf = 1e18; 
LL n,m,a[N],b[N];
LL work(LL k) {
    LL res = inf;
    for(int i = 1;i <= n;i++) {
        for(int j = i + 1;j <= n;j++) {
            res = min((a[i]+a[j])*k+b[i]+b[j],res);
        }
    }
    return res;
}
int main() {
    n = read();m = read();
    for(int i = 1;i <= n;i++) a[i] = read(),b[i] = read();
    LL L = 1,R = m;
    while(L + 100 <= R) {
        LL mid1 = L + (R - L) / 3;
        LL mid2 = R - (R - L) / 3;
        if(work(mid1) > work(mid2)) R = mid2;
        else L = mid1;
    }
    LL ans = -inf;
    for(int i = L ;i <= R;i++) ans = max(ans,work(i));
    cout << ans << endl;
    return 0;
}