---
# System prepended metadata

title: AtCoder abc023_d
tags: [' binary search', atcoder]

---

---
title: AtCoder abc023_d
tags: atcoder, binary search
---


```c++
// https://atcoder.jp/contests/abc023/tasks/abc023_d
#include <iostream>
#include <list>
#include <unordered_map>
#include <vector>

using namespace std;
using ll = int64_t;
using pll = pair<ll, ll>;

pll ary[100000];
ll toSort[100000];

bool check(ll mid, int n) {
  for (int i = 0; i < n; i++)
    toSort[i] = (mid - ary[i].first) / ary[i].second;
  sort(toSort, toSort + n);
  for (int i = 0; i < n; i++) {
    if (i > toSort[i])
      return false;
  }
  return true;
}

int main() {
  int n;
  ll x = 0, y = 0;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> ary[i].first >> ary[i].second;
    ll tmp = ary[i].first + ary[i].second * n;
    y = max(y, tmp);
    x = max(x, ary[i].first - 1);
  }
  while (x < y - 1) {
    ll mid = (x + y) / 2;
    if (check(mid, n))
      y = mid;
    else
      x = mid;
  }
  cout << y << endl;
}
```