# 問題

https://atcoder.jp/contests/abc104/tasks/abc104_c

# 入力

$D G$
$p_1 c_1$
...
$p_D c_D$

問題ランク数 $D$ 、目標スコア $G$ と $D$ 個の問題セットが与えられます.
問題セットは問題数 $p_i$ と全問解いた場合のボーナス $c_i$ からなります.
問題セット $i$ の点数は $100 \times i$ です.

# 出力

$G$ を達成するような最小の問題数を答える問題です.

# 解説

問題数の最大値は $10^3$ 個です.
なので計算量を1秒に間に合う $10^8$ に収めるには最大でも $O(N^2 \log N)$ 程度に抑える必要があります.

すべての問題について解くか否かの組み合わせを考えればその中で最も問題数が少なくて目標スコアを満たすものが答えになります.
当然答えは求まりますが、 $2^n$ となり間に合いません.

そこで得点は問題のランクが高いほど高くなることに着目します.
ボーナスが無いとすると貪欲法的に最後の問題から目標スコアに達するまで解いていくのが答えはなずです.
これは $O(N)$ で解けます.
今回はボーナスがあるので、得点が高い問題の部分点よりも低い問題のボーナスの方が高い可能性があります.
この方法は使えません.

そこで今度は問題１つずつに着目するのではなくランクに着目してみます.
ランクは最大で $10$ 個なのでこれで解ければビット全探索でも計算量 $2^10$ で間に合います.

すべてのランクについて解くか否かの組み合わせをすべて考えます.
解く、とは全問解いてボーナスまでもらうことを指します.
解かない、とは１問も解かないことを指します.
どちらのケースでも、目標スコアに足りていなければ解かれていないランクの内で最大のものから部分的に解いて良いこととします（ $O(1)$ ）.
部分的に解く、とは問題数の内数問解くがボーナスは得られないことを指します.

これで正解が得られます.
部分的に解くのは１ランクのみで良くて $O(1)$ で可能な理由は、２ランク以上部分的に解くよりはまず優先して得点が高い方の１ランクを集中して解いた方が常に良いからです.
部分的に解くのでボーナスは考慮する必要がなく貪欲法的です.

# 計算量

$O(2^D)$

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define MAX_D 11

struct Rank {
  Int numProblems, score, bonus;

  Rank(): numProblems(0), score(0), bonus(0) {}

  Rank(Int n, Int s, Int b): numProblems(n), score(s), bonus(b) {
  }
};

Int D, G, c, p;
Rank ranks[MAX_D];

struct State {
  Int index = 0, numTaken = 0, score = 0, partialIndex = 0;

  State() {
  }

  bool success() {
    return score >= G;
  }

  bool end() {
    return index >= D;
  }

  State takePart() {
    State copy = *this;
    Int need = (G - score) / ranks[index].score;
    if (need > ranks[index].numProblems) return copy;
    copy.score += ranks[index].score * need;
    copy.numTaken += need;
    return copy;
  }

  State take() {
    State copy = *this;
    copy.score += ranks[index].score * ranks[index].numProblems + ranks[index].bonus;
    copy.numTaken += ranks[index].numProblems;
    return copy;
  }

  State inc() {
    State copy = *this;
    copy.index++;
    return copy;
  }
};

void input() {
  cin >> D >> G;
  loop(d,1,D+1) {
    cin >> p >> c;
    ranks[d-1] = Rank(p, 100*d, c);
  }
}

State dfs(State state) {
  if (state.success() || state.end()) return state;
  if (state.takePart().success()) return state.takePart();

  State not_take = dfs(state.inc());
  State take = dfs(state.take().inc());
  if (not_take.success() && take.success())
    return (not_take.numTaken < take.numTaken) ? not_take : take;
  if (take.success()) return take;
  else return not_take;
}

void solve() {
  State init;
  State result = dfs(init);
  cout << result.numTaken << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}

ABC104 C - All Green