種類以上のお菓子を買うことは、いくつかのお菓子の値段の減少分を無駄にしてしまうため、考えなくてよいです。
よって、 種類のお菓子を購入するのが最適です。
それぞれのお菓子を 個購入したときの値段は等差数列の和の公式を利用すれば で高速に求められます。
したがって、この問題を全体で で解くことができました。
実装するときには、お菓子の値段が途中で となる場合に注意してください。
実装例(C++)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, k;
cin >> n >> k;
vector<long long> a(n), b(n);
for(int i = 0; i < n; i++){
cin >> a[i] >> b[i];
}
long long ans = 2e18;
for(int i = 0; i < n; i++){
long long cost = 0, count = (a[i] + b[i] - 1) / b[i];
if(k < count){
cost += k * (2 * a[i] + (k - 1) * -b[i]) / 2;
}else{
cost = count * (2 * a[i] + (count - 1) * -b[i]) / 2;
cost += (k - count);
}
ans = min(ans, cost);
}
cout << ans << endl;
}