Source Code
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll N = 1000000;
const ll M = N * N;

ll k;
int n;
vector<pll> a;

int main() {
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        ll x, y;
        scanf("%lld%lld", &x, &y);
        if (x <= N && x * x <= k) {
            a.emplace_back(y, x);
        }
    }
    sort(a.begin(), a.end());

    ll old = 0;
    ll answer = 0;
    vector<ll> subs;
    vector<ll> newsubs;
    for (pll p : a) {
        ll y = p.second;
        ll x = y * y;

        ll current = old;
        if (x <= k) {
            newsubs.push_back(x);
            current += k / x;
        }
        for (ll z : subs) {
            if (abs(z * y) <= k && abs(z * x) <= k) {
                newsubs.push_back(-z * x);
                current += k / (-z * x);
            }
        }

        subs = newsubs;

        ll now = current - old;
        answer += now * p.first;
        old = current;
    }

    cout << answer << endl;
}
Copy
Number of the Beast Baraa_Armoush
GNU G++17
1091 ms
3.0 MB
Time Limit Exceeded
Test Case #1
0 ms
360 KB
Accepted
Input
4 10
2 300
3 66
5 100
13 32
Output
666
Judge Output
666
Checker Message
1 number(s): "666"
Test Case #2
0 ms
404 KB
Accepted
Input
2 50
3 10
7 21
Output
71
Judge Output
71
Checker Message
1 number(s): "71"
Test Case #3
38 ms
1.2 MB
Accepted
Input
8944 1000000000000
530851 634109
437629 135449
760841 608005
987979 505317
567187 797505
115057 581792
986287 132112
788677 472337
209929 417283
972313 694722
65809 400083
710887 970135
432959 268565
920039 761441
375703 505835
988439 938996
257473 ...
Output
39179400996329
Judge Output
39179400996329
Checker Message
1 number(s): "39179400996329"
Test Case #4
1091 ms
3.0 MB
Time Limit Exceeded
Input
52876 1000000000000
774601 578667
323131 777063
726521 116978
526049 7406
439849 428478
257993 853903
926099 703420
650543 859979
445657 85973
713653 866195
201973 968679
393709 554653
695377 749686
970817 300795
175631 382628
17291 977384
453659 21...
Output

Judge Output
47954264298367020
Checker Message