题目描述

样例

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define int long long

const int N = 100010;

int a[N],b[N];
int n,m;

bool check(int mid)
{
    int cnt = 0;
    for(int i = 0 ; i < n ; i ++)
    {
        if(a[i] >= mid)
            cnt += (a[i] - mid) / b[i] + 1;
    }
    return cnt >= m;
}

signed main()
{
    cin >> n >> m;

    for(int i = 0 ; i < n ; i++) scanf("%lld%lld",&a[i],&b[i]);

    int l = 0 , r = 1e6;
    while(l < r)
    {
        int mid = (l + r + 1 )>> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }

    int res = 0 , cnt = 0;
    for(int i = 0 ; i < n ; i++)
    {
        if(a[i] >= r)
        {
            int t = (a[i] - r)/b[i] + 1;
            cnt += t;
            res += t*a[i] - (t-1)*t*b[i]/2;
        }
    }
    cout << res - (cnt - m)*r << endl;
}