#1143656 (C++17) No.3422 Sazanka's hobby

• 問題: No.3422 Sazanka's hobby
• ユーザー: 9223372036854775807
• 提出日時: 2026-01-11 13:50:10
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 410 ms / 2,000 ms
• コード長: 23,409 bytes
• コンパイル時間: 2,210 ms
• コンパイル使用メモリ: 178,680 KB
• 実行使用メモリ: 12,896 KB
• 最終ジャッジ日時: 2026-01-11 13:50:16
• 合計ジャッジ時間: 5,915 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
other	AC * 13

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
#include <functional>
#include <random>
#include <bitset>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define vall(A) A.begin(), A.end()
#define vin(A) for (ll iiii = 0, sz = A.size(); iiii < sz; iiii++){cin >> A[iiii];}
#define vout(A) for(ll iiii = 0, sz = A.size(); iiii < sz; iiii++){cout << A[iiii] << " \n"[iiii == sz-1];}
#define vout2d(A) for (ll iiii = 0, HHHH = A.size(), WWWW = (A.empty() ? 0 : A[0].size()); iiii < HHHH; iiii++){for (ll jjjj = 0; jjjj < WWWW; jjjj++){cout << A[iiii][jjjj] << " \n"[jjjj==WWWW-1];}}
#define vsum(A) [&](const auto &vveecc){ll ssuumm = 0; for(auto &vvaalluuee : vveecc){ssuumm += vvaalluuee;} return ssuumm;}(A)
#define adjustedvin(A) for (ll iiii = 1, sz = A.size(); iiii < sz; iiii++){cin >> A[iiii];}
#define adjustedvout(A) for(ll iiii = 1, sz = A.size(); iiii < sz; iiii++){cout << A[iiii] << " \n"[iiii == sz-1];}
#define adjustedvout2d(A) for (ll iiii = 1, HHHH = A.size(), WWWW = (A.empty() ? 0 : A[0].size()); iiii < HHHH; iiii++){for (ll jjjj = 1; jjjj < WWWW; jjjj++){cout << A[iiii][jjjj] << " \n"[jjjj==WWWW-1];}}
vector<ull> pow2ll{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904, 9223372036854775808ull};
vector<ull> pow10ll{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000, 10000000000000000000ull};
vector<ll> di{0,1,0,-1};
vector<ll> dj{1,0,-1,0};


namespace a1073741824{

//library
namespace math{

//math.hpp
/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる。
/// @param a 
/// @param b 
/// @param m 
/// @return a^b%m
ll modpow(ll a, ll b, ll m){
    ll t = a%m;
    ll ans = 1;
    while (b > 0){
        if (b%2){
            ans = (ans*t)%m;
        }
        b /= 2;
        t = (t*t)%m;
    }
    return ans;
}

/// @brief a^nを返す。bに関して線形時間で計算できる。
/// @param a 
/// @param n
/// @param m 
/// @return a^n
ll powll(ll a, ll n){
    ll r = 1;
    for (ll i = 1; i <= n; i++){
        r *= a;
    }
    return r;
}

/// @brief 正の整数Nを素因数分解する
/// @param N
/// @return vector<vector<ll> {{素因数1,個数}, {素因数2,個数}, {素因数3,個数}...}
vector<vector<ll>> p_fact(ll N){
    if (N == 1){
        return vector<vector<ll>> {{1,1}};
    }
    vector<vector<ll>> R;//戻り値用リスト

    const ll M = N;
    for (ll i = 2; i <= sqrtl(M); i++){
        if (N % i == 0){
            ll divide_count = 0;
            while (N % i == 0){
                divide_count++;
                N /= i;
            }
            R.push_back(vector<ll> {i,divide_count});
        }
    }
    if (N != 1){
        R.push_back(vector<ll> {N,1});
    }
    return R;
}

/// @brief 二次元ベクトル表記の素因数分解リストを受け取って約数の和を求める
/// @param vv 
/// @return 約数の和
ll sum_of_divisor(vector<vector<ll>> vv){
    if (vv[0][0] == 1){
        return 1;
    }
    ll R = 1;
    for (vector<ll> x : vv){
        R *= ((ll)powl(x[0],x[1]+1) - 1)/(x[0] - 1);
    }
    return R;
}

/// @brief 二次元ベクトル表記の素因数分解リストを受け取って約数の種類を求める
/// @param vv 
/// @return 約数の種類
ll kind_of_divisor(vector<vector<ll>> vv){
    ll R = 1;
    for (vector<ll> x : vv){
        R *= x[1]+1;
    }
    return R;
}

/// @brief 1のみを含むデフォルトリストdと、素因数分解の結果pを受け取って、dを約数リストに変換する。
/// @return ない
void search_divisor(vector<ll> &d, vector<vector<ll>> &p, ll depth = 0){
    if (depth == p.size()){
        sort(vall(d));
        return;
    }
    ll t = d.size();
    for (ll i = 1; i <= p[depth][1]; i++){
        for (ll j = 0; j < t; j++){
            d.push_back(d[j]*powll(p[depth][0], i));
        }
    }
    search_divisor(d, p, depth+1);
}

/// @brief 有理数のceilを求める
/// @param y 
/// @param x 
/// @return ceil(y/x)
ll cefrac(ll y, ll x);

/// @brief 有理数のfloorを求める
/// @param y
/// @param x 
/// @return floor(y/x)
ll flfrac(ll y, ll x){
    if ((x^y) > 0){
        x = abs(x);
        y = abs(y);
        return (y-(y%x))/x;
    }
    else if ((x^y) < 0){
        x = abs(x);
        y = abs(y);
        return -cefrac(y,x);
    }
    else{
        return y/x;
    }
}

ll cefrac(ll y, ll x){
    if ((x^y) > 0){
        x = abs(x);
        y = abs(y);
        if (y%x == 0){
            return y/x;
        }
        else return 1 + (y-(y%x))/x;
    }
    else if ((x^y) < 0){
        x = abs(x);
        y = abs(y);
        return -flfrac(y,x);
    }
    else{
        return y/x;
    }
}

ll flsqrt(ll N){
    if (N){
        ll ok = 1;
        ll ng = min(N,2000000000LL);
        while (ng - ok >= 2){
            ll mid = (ok+ng)/2;
            if (mid*mid <= N){
                ok = mid;
            } 
            else{
                ng = mid;
            }
        }
        return ok;
    }
    else{return 0;}
}

/// @brief エラトステネスの篩
struct Eratosthenes{
    vector<ll> P_List;
    vector<bool> is_prime;
    vector<ll> min_factor;
    Eratosthenes(ll N) : is_prime(N+1,1), min_factor(N+1,-1){
        is_prime[1] = 0;
        min_factor[1] = 1;
        for (ll i = 2; i <= N; i++){
            if (is_prime[i]){
                P_List.push_back(i);
                min_factor[i] = i;
                for (ll j = 2*i; j <= N; j += i){
                    is_prime[j] = 0;
                    if (min_factor[j] == -1){
                        min_factor[j] = i;
                    }
                }
            }
        }
    }

    void chase_prime(const ll &reference, ll x, vector<vector<vector<ll>>> &r){
        if (r[reference].empty() || min_factor[x] != r[reference].back()[0]){
            r[reference].push_back({min_factor[x], 1});
        }
        else{
            r[reference].back()[1]++;
        }

        if (x != min_factor[x]){
            chase_prime(reference, x/min_factor[x], r);
        }
    }

    vector<vector<vector<ll>>> p_fact(ll N){
        vector<vector<vector<ll>>> r(N+1);
        r[1].push_back({1,1});
        for (ll i = 2; i <= N; i++){
            chase_prime(i, i, r);
        }
        return r;
    }

};

/// @brief 一次不定方程式ax+by=1の解を1つ見つける
/// @param a 
/// @param b 
/// @return {x,y}
pair<ll,ll> axby1(ll a, ll b){
    if (a == 1 or b == 1){
        if (a == 1){
            return {1-b,1};
        }
        else{
            return {1,1-a};
        }
    }
    else if (a>b){
        auto p = axby1(a%b, b);
        return {p.first, p.second - p.first*(a/b)};
    }
    else{
        swap(a,b);
        auto p = axby1(a%b, b);
        return {p.second - p.first*(a/b), p.first};
    }
}

/// @brief 1/a mod Mを求める
/// @param a 
/// @param M 
/// @return 1/a mod M
ll inverse_mod(ll a, ll M){
    if (__gcd(a,M) != 1){
        return -1;
    }
    return (M+(axby1(a,M).first)%M)%M;
}

/// @brief modint
template<ll M>
struct mll{
    ll val;
    mll(const ll &x){
        val = x%M;
    }
    void operator=(const ll &x){
        val = x%M;
    }
    void operator=(const mll &a){
        val = a.val;
    }
    
    mll operator+(const mll &a){
        return mll(val+a.val);
    }
    void operator+=(const mll &a){
        val = (val+a.val)%M;
    }
    mll operator+(const ll &a){
        return mll(val+a);
    }
    void operator+=(const ll &a){
        val = (val+a)%M;
    }

    mll operator-(const mll &a){
        return mll(M+val-a.val);
    }
    void operator-=(const mll &a){
        val = (M+val-a.val)%M;
    }
    mll operator-(const ll &a){
        return mll(M+val-a);
    }
    void operator-=(const ll &a){
        val = (M+val-a)%M;
    }

    mll operator*(const mll &a){
        return mll(val*a.val);
    }
    void operator*=(const mll &a){
        val = (val*a.val)%M;
    }
    mll operator*(const ll &a){
        return mll(val*a);
    }
    void operator*=(const ll &a){
        val = (val*a)%M;
    }

    mll operator/(const mll &a){
        return mll(val*inverse_mod(a.val,M));
    }
    void operator/=(const mll &a){
        val = (val*inverse_mod(a.val,M))%M;
    }
    mll operator/(const ll &a){
        return mll(val*inverse_mod(a,M));
    }
    void operator/=(const ll &a){
        val = (val*inverse_mod(a,M))%M;
    }
};

//階乗前計算による二項係数mod998244353
struct factorialncr{
    private: vector<ll> factorialmod;
    private: ll N_MAX_N_MAX;
    public:
    factorialncr(const ll &N_MAX){
        N_MAX_N_MAX = N_MAX;
        factorialmod = vector<ll>(N_MAX+1);
        factorialmod[0] = 1;
        for (ll i = 1; i <= N_MAX; i++){
            factorialmod[i] = (i*factorialmod[i-1])%998244353;
        }
    }

    ll nCr(ll n, ll r){
        if (r < 0 || n < r || n > N_MAX_N_MAX){
            return 0;
        }
        return (factorialmod[n]*inverse_mod((factorialmod[n-r]*factorialmod[r])%998244353,998244353))%998244353;
    }
};

//表の前計算による二項係数modM
struct tablencr{
    private: vector<vector<ll>> ncrmodlist;
    private: ll N_MAX_N_MAX;
    public:
    tablencr(const ll &N_MAX, const ll &M){
        N_MAX_N_MAX = N_MAX;
        ncrmodlist = vector<vector<ll>> (5001, vector<ll>(5001,0));
        ncrmodlist[0][0] = 1;
        for (ll i = 1; i <= 5000; i++){
            for (ll j = 0; j <= i; j++){
                if (j == 0 || j == i){
                    ncrmodlist[i][j] = 1;
                }
                else{
                    ncrmodlist[i][j] = (ncrmodlist[i-1][j-1] + ncrmodlist[i-1][j])%M;
                }
            }
        }
    }
    ll nCr(ll n, ll r){
        if (r < 0 || n < r || n > N_MAX_N_MAX){
            return 0;
        }
        return ncrmodlist[n][r];
    }
};

//matrix.hpp
/// @brief 64bit整数行列。自動でmod998244353などを取ってくれる。
/// @tparam MMOODD
template<ll MMOODD>
struct matrixll{
    vector<vector<ll>> M;
    ll H,W;
    /// @brief N次単位行列を生成
    /// @param N 
    matrixll(ll N){
        H = N;W = N;
        M = vector<vector<ll>>(N,vector<ll>(N,0));
        for (ll i = 0; i < N; i++){
            M[i][i] = 1;
        }
    }
    /// @brief h×w型の、全要素がvの行列を生成
    /// @param h 
    /// @param w 
    /// @param v 
    matrixll(ll h, ll w, ll v){
        H = h;
        W = w;
        M = vector<vector<ll>>(H,vector<ll>(W,v));
    }
    /// @brief 2次元配列を用いて行列を生成
    /// @param A 
    matrixll(vector<vector<ll>> &A){
        M = A;
        H = A.size();
        W = A[0].size();
    }
    matrixll operator+(const matrixll &T){
        if (H != T.H  || W != T.W){
            cerr << "size error\n";
            assert(false);
        }
        matrixll ans(M);
        for (ll i = 0; i < H; i++){
            for (ll j = 0; j < W; j++){
                ans.M[i][j] += T.M[i][j];
                ans.M[i][j] %= MMOODD;
            }
        }
        return ans;
    }
    void operator+=(const matrixll &T){
        if (H != T.H  || W != T.W){
            cerr << "size error\n";
            assert(false);
        }
        for (ll i = 0; i < H; i++){
            for (ll j = 0; j < W; j++){
                M[i][j] += T.M[i][j];
                M[i][j] %= MMOODD;
            }
        }
    }
    matrixll operator-(const matrixll &T){
        if (H != T.H  || W != T.W){
            cerr << "size error\n";
            assert(false);
        }
        matrixll ans(M);
        for (ll i = 0; i < H; i++){
            for (ll j = 0; j < W; j++){
                ans.M[i][j] -= T.M[i][j];
                ans.M[i][j] += MMOODD;
                ans.M[i][j] %= MMOODD;
            }
        }
        return ans;
    }
    void operator-=(const matrixll &T){
        if (H != T.H  || W != T.W){
            cerr << "size error\n";
            assert(false);
        }
        for (ll i = 0; i < H; i++){
            for (ll j = 0; j < W; j++){
                M[i][j] -= T.M[i][j];
                M[i][j] += MMOODD;
                M[i][j] %= MMOODD;
            }
        }
    }
    matrixll operator*(const matrixll &T){
        if (W != T.H){
            cerr << "size error\n";
            assert(false);
        }
        matrixll ans(H,T.W,0);
        for (ll i = 0; i < H; i++){
            for (ll j = 0; j < T.W; j++){
                for (ll k = 0; k < W; k++){
                    ans.M[i][j] += M[i][k]*T.M[k][j];
                    ans.M[i][j] %= MMOODD;
                }
            }
        }
        return ans;
    }
    void operator*=(const matrixll &T){
        if (W != T.H){
            cerr << "size error\n";
            assert(false);
        }
        matrixll ans(H,T.W,0);
        for (ll i = 0; i < H; i++){
            for (ll j = 0; j < T.W; j++){
                for (ll k = 0; k < W; k++){
                    ans.M[i][j] += M[i][k]*T.M[k][j];
                    ans.M[i][j] %= MMOODD;
                }
            }
        }
        W = T.W;
        M = ans.M;
    }
    matrixll operator*(const ll &c){
        matrixll ans(H,W,0);
        for (ll i = 0; i < H; i++){
            for (ll j = 0; j < W; j++){
                ans.M[i][j] = M[i][j] * c;
                ans.M[i][j] %= MMOODD;
            }
        }
        return ans;
    }
    void operator*=(const ll &c){
        for (ll i = 0; i < H; i++){
            for (ll j = 0; j < W; j++){
                M[i][j] *= c;
                M[i][j] %= MMOODD;
            }
        }
    }

    /// @brief A^Nを返す。
    /// @param A 
    /// @param N 
    /// @return A^N
    matrixll matrixmodpow(ll N){
        matrixll R(H);
        matrixll A(M);
        for (ll i = 0; i < H; i++){
            for (ll j = 0; j < H; j++){
                A.M[i][j] %= MMOODD;
            }
        }
        if (N){
            while (N){
                if (N%2){
                    R *= A;
                }
                A *= A;
                N /= 2;
            }
            return R;
        }
        else{
            return R;
        }
    }
};

//quatient_range.hpp
/// @brief sum[i=1 ~ i=N] i^a * (floor(M/i))^b を計算する
/// @param N 
/// @param M 
/// @param a 
/// @param b 
/// @return 
ll inv_floor_sum(ll N, ll M, ll a ,ll b){
    auto floorsqrt = [](ll N){
        ll ok = 1;
        ll ng = min(N,2000000000LL);
        while (ng - ok >= 2){
            ll mid = (ok+ng)/2;
            if (mid*mid <= N){
                ok = mid;
            }
            else{
                ng = mid;
            }
        }
        return ok;
    };
    auto lpowl = [](ll x, ll N){
        ll r = 1;
        for (ll i = 1; i <= N; i++){
            r *= x;
        }
        return r;
    };
    
    vector<vector<ll>> nCrtable(a+2,vector<ll>(a+2,0));
    nCrtable[0][0] = 1;
    for (ll i = 1; i <= a+1; i++){
        for (ll j = 0; j <= i; j++){
            if (j == 0 || j == i){
                nCrtable[i][j] = 1;
            }
            else{
                nCrtable[i][j] = nCrtable[i-1][j-1] + nCrtable[i-1][j];
            }
        }
    }

    function<ll(ll,ll)> sum = [&](ll n, ll l){
        if (l == 0){
            return n;
        }
        if (l == 1){
            return n*(n+1)/2;
        }
        if (l == 2){
            return n*(n+1)*(2*n+1)/6;
        }
        ll T = 0;
        for (ll i = 0; i < l; i++){
            T += nCrtable[l+1][i]*sum(n,i);
        }
        return (lpowl(n+1,l+1)-1-T)/(l+1);
    };


    ll ans = 0;
    ll rootM = floorsqrt(M);
    
    if (N <= M / rootM){//Nが小さいときはそのまま計算して値を返す
        for (ll i = 1; i <= N; i++){
            ans += lpowl(i,a)*lpowl(M/i,b);
        }
        return ans;
    }

    //それ以外の場合は主客転倒を行う

    for (ll i = 1; i <= M/rootM; i++){//最初の方をそのまま足す。
        ans += lpowl(i,a)*lpowl(M/i,b);
    }
    for (ll i = rootM-1; i > M/N; i--){
        ans += lpowl(i,b)*(sum(M/i,a) - sum(M/(i+1),a));
    }
    ans += lpowl(M/N,b)*(sum(N,a) - sum(M/((M/N)+1), a));

    return ans;
}


//convolution.hpp
vector<ll> powroot998244353{1LL, 998244352LL, 911660635LL, 372528824LL, 69212480LL, 381091786LL, 515872972LL, 273395035LL, 469477650LL, 503794470LL, 464513504LL, 558899782LL, 504969456LL, 840897051LL, 539927980LL, 417009993LL, 725461291LL, 456548895LL, 712494065LL, 542639453LL, 768214923LL, 303507821LL, 438914733LL, 761881641};
vector<ll> powrootinv998244353{1LL, 998244352LL, 86583718LL, 509520358LL, 661054123LL, 863921598LL, 323451984LL, 689146517LL, 379690232LL, 240519260LL, 899368279LL, 920065956LL, 588792270LL, 118574449LL, 847593593LL, 858760106LL, 987418793LL, 177938570LL, 753608159LL, 786906984LL, 331540181LL, 655706071LL, 268754442LL, 191076546};
vector<ll> powroot1224736769{1LL, 1224736768LL, 24506215LL, 992888437LL, 853017291LL, 235319402LL, 269744380LL, 157861287LL, 894223137LL, 600648668LL, 1091208103LL, 382541006LL, 12818149LL, 149218560LL, 746299392LL, 405692663LL, 633223136LL, 672327338LL, 992917013LL, 758198491LL, 1079610480LL, 1056667043LL, 1039331205LL, 1026803890LL, 449603200};
vector<ll> powrootinv1224736769{1LL, 1224736768LL, 1200230554LL, 961581489LL, 796105727LL, 1023008969LL, 406386483LL, 251411652LL, 655108271LL, 1145368249LL, 780593535LL, 38041180LL, 816166160LL, 659160240LL, 1200430513LL, 392462252LL, 15561184LL, 893027826LL, 928760284LL, 497993173LL, 529117122LL, 637457654LL, 931394937LL, 823596420LL, 55047034};

vector<ll> DFT998244353(vector<ll> X, ll K, bool inverse = false){
    if (K == 1){
        return vector<ll>{(X[0]+X[1])%998244353, (998244353+X[0]-X[1])%998244353};
    }

    vector<ll> even(1LL<<(K-1));
    vector<ll> odd(1LL<<(K-1));
    for (ll i = 0; i < (1LL<<(K-1)); i++){
        even[i] = (X[i] + X[(1LL<<(K-1))+i])%998244353;
    }
    ll temp = 1;
    if (inverse){
        for (ll i = 0; i < (1LL<<(K-1)); i++){
            odd[i] = (temp*(998244353 + X[i] - X[(1LL<<(K-1))+i]))%998244353;
            temp = (temp*powrootinv998244353[K])%998244353;
        }
    }
    else{
        for (ll i = 0; i < (1LL<<(K-1)); i++){
            odd[i] = (temp*(998244353 + X[i] - X[(1LL<<(K-1))+i]))%998244353;
            temp = (temp*powroot998244353[K])%998244353;
        }
    }

    even = DFT998244353(even,K-1,inverse);
    odd = DFT998244353(odd,K-1,inverse);
    for (ll i = 0; i < (1LL<<K); i++){
        if (i%2){
            X[i] = odd[i/2];
        }
        else{
            X[i] = even[i/2];
        }
    }
    return X;
}
vector<ll> DFT1224736769(vector<ll> X, ll K, bool inverse = false){
    if (K == 1){
        return vector<ll>{(X[0]+X[1])%1224736769, (1224736769+X[0]-X[1])%1224736769};
    }

    vector<ll> even(1LL<<(K-1));
    vector<ll> odd(1LL<<(K-1));
    for (ll i = 0; i < (1LL<<(K-1)); i++){
        even[i] = (X[i] + X[(1LL<<(K-1))+i])%1224736769;
    }
    ll temp = 1;
    if (inverse){
        for (ll i = 0; i < (1LL<<(K-1)); i++){
            odd[i] = (temp*(1224736769 + X[i] - X[(1LL<<(K-1))+i]))%1224736769;
            temp = (temp*powrootinv1224736769[K])%1224736769;
        }
    }
    else{
        for (ll i = 0; i < (1LL<<(K-1)); i++){
            odd[i] = (temp*(1224736769 + X[i] - X[(1LL<<(K-1))+i]))%1224736769;
            temp = (temp*powroot1224736769[K])%1224736769;
        }
    }

    even = DFT1224736769(even,K-1,inverse);
    odd = DFT1224736769(odd,K-1,inverse);
    for (ll i = 0; i < (1LL<<K); i++){
        if (i%2){
            X[i] = odd[i/2];
        }
        else{
            X[i] = even[i/2];
        }
    }
    return X;
}

vector<ll> convolution998244353(vector<ll> A, vector<ll> B){

    if (min(A.size(), B.size()) <= 60) {
        if (A.size() < B.size()) {
            swap(A, B);
        }
        std::vector<ll> ans(A.size() + B.size() - 1);
        for (int i = 0; i < A.size(); i++) {
            for (int j = 0; j < B.size(); j++) {
                ans[i + j] += A[i] * B[j];
            }
        }
        for (auto &v : ans){
            v %= 998244353;
        }
        return ans;
    }

    ll N = A.size()+B.size()-1;
    ll log2N = 0;
    while ((1LL<<log2N) < N){
        log2N++;
    }

    while (A.size() < (1LL<<log2N)){
        A.push_back(0);
    }
    while (B.size() < (1LL<<log2N)){
        B.push_back(0);
    }

    A = DFT998244353(A,log2N);
    B = DFT998244353(B,log2N);
    vector<ll> C((1LL<<log2N),0);
    for (ll i = 0; i < (1LL<<log2N); i++){
        C[i] = (A[i]*B[i])%998244353;
    }
    C = DFT998244353(C,log2N,1);
    ll invpow2log2N = inverse_mod((1LL<<log2N),998244353);
    for (ll i = 0; i < (1LL<<log2N); i++){
        C[i] = (C[i]*invpow2log2N)%998244353;
    }
    return C;
}
vector<ll> convolution1224736769(vector<ll> A, vector<ll> B){

    if (min(A.size(), B.size()) <= 60) {
        if (A.size() < B.size()) {
            swap(A, B);
        }
        std::vector<ll> ans(A.size() + B.size() - 1);
        for (int i = 0; i < A.size(); i++) {
            for (int j = 0; j < B.size(); j++) {
                ans[i + j] += A[i] * B[j];
            }
        }
        for (auto &v : ans){
            v %= 1224736769;
        }
        return ans;
    }

    ll N = A.size()+B.size()-1;
    ll log2N = 0;
    while ((1LL<<log2N) < N){
        log2N++;
    }

    while (A.size() < (1LL<<log2N)){
        A.push_back(0);
    }
    while (B.size() < (1LL<<log2N)){
        B.push_back(0);
    }

    A = DFT1224736769(A,log2N);
    B = DFT1224736769(B,log2N);
    vector<ll> C((1LL<<log2N),0);
    for (ll i = 0; i < (1LL<<log2N); i++){
        C[i] = (A[i]*B[i])%1224736769;
    }
    C = DFT1224736769(C,(1LL<<log2N),1);
    ll invpow2log2N = inverse_mod((1LL<<log2N),1224736769);
    for (ll i = 0; i < 1048576; i++){
        C[i] = (C[i]*invpow2log2N)%1224736769;
    }
    return C;
}

}

}
using namespace a1073741824;






int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    ll N,M;
    cin >> N >> M;

    vector<ll> A;
    for (ll i = 0; i < N; i++){
        ll a,b;
        cin >> a >> b;
        A.push_back(max(0LL, math::flfrac(M-a, b)));
    }

    sort(vall(A));
    //vout(A);

    for (ll k = 1;; k++){
        bool ok = true;
        for (ll i = 0; i < N; i += k){
            if (i/k > A[i]){
                ok = false;
            }
        }
        if (ok){
            cout << k << "\n";
            return 0;
        }
    }

}