1217B - Zmei Gorynich - CodeForces Solution

//بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template<typename T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define Samo7a ios_base::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);
#define re return
#define FX(n) fixed << setprecision(n)
#define endl '\n'
#define sz(v) (int) v.size()
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define pb push_back
#define eb emplace_back
#define pi acos(-1)
#define F first
#define S second
const int N = 2e3 + 10, MOD = 1e9 + 7;
const int dx[]{1, -1, 0, 0, 1, -1, 1, -1};
const int dy[]{0, 0, 1, -1, 1, -1, -1, 1};

inline void debugMode() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}

//الشَّيْطَانُ يَعِدُكُمُ الْفَقْرَ وَيَأْمُرُكُم بِالْفَحْشَاءِ ۖ وَاللَّهُ يَعِدُكُم مَّغْفِرَةً مِّنْهُ وَفَضْلًا ۗ وَاللَّهُ وَاسِعٌ عَلِيمٌ (268)
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
/*
 id: 7
 idea: if we shoot s shoots so x will decrease d[i] * s and will increase s-1 * h[i]
 so brute force on the best pair and choose the one more extra shoot = max d[i]
*/

void TestCase() {
    int n, x;
    cin >> n >> x;
    int d[n], h[n], mx = -1;
    bool bad = 1;
    for (int i = 0; i < n; i++) {
        cin >> d[i] >> h[i];
        mx = max(mx, d[i]);
        bad &= (d[i] <= h[i] and d[i] < x);
    }
    if (bad) {
        cout << -1 << endl;
        re;
    }
    if (mx >= x) {
        cout << 1 << endl;
        re;
    }
    ll mn = 1e18;
    for (int i = 0; i < n; i++) {
        ll l = 0, r = 1e10, ans = 1e10;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (mid * d[i] + mx >= (x + mid * h[i]))
                ans = mid, r = mid - 1;
            else
                l = mid + 1;
        }
        mn = min(mn, ans + 1);
    }
    cout << mn << endl;
}

int main() {
    Samo7a
    debugMode();
    int t = 1;
    cin >> t;
    while (t--) {
        TestCase();
    }
    re 0;
}