100 #ABC104C. [ABC104C] All Green

[ABC104C] All Green

题目描述

プログラミングコンペティションサイト AtCode は、アルゴリズムの問題集を提供しています。 それぞれの問題には、難易度に応じて点数が付けられています。 現在、1 1 以上 D D 以下のそれぞれの整数 i i に対して、100i 100i 点を付けられた問題が pi p_i 問存在します。 これらの p1 +  + pD p_1\ +\ …\ +\ p_D 問が AtCode に収録された問題のすべてです。

AtCode のユーザーは 総合スコア と呼ばれる値を持ちます。 ユーザーの総合スコアは、以下の 2 2 つの要素の和です。

  • 基本スコア: ユーザーが解いた問題すべての配点の合計です。
  • コンプリートボーナス: 100i 100i 点を付けられた pi p_i 問の問題すべてを解いたユーザーは、基本スコアと別にコンプリートボーナス ci c_i 点を獲得します (1 < = i < = D) (1\ <\ =\ i\ <\ =\ D)

AtCode の新たなユーザーとなった高橋くんは、まだ問題を 1 1 問も解いていません。 彼の目標は、総合スコアを G G 点以上にすることです。 このためには、少なくとも何問の問題を解く必要があるでしょうか?

输入格式

入力は以下の形式で標準入力から与えられる。

D D G G p1 p_1 c1 c_1 : : pD p_D cD c_D

输出格式

総合スコアを G G 点以上にするために解く必要のある最小の問題数を出力せよ。なお、この目標は必ず達成可能である(制約を参照のこと)。

题目大意

DD 套题目,难度从 11DD ,第 ii 套题目有 pip_i 道,分值均为 i×100i \times 100,全部做完再奖励 cic_i 分,求至少拿到 GG 分至少要刷多少道题?

2 700
3 500
5 800
3
2 2000
3 500
5 800
7
2 400
3 500
5 800
2
5 25000
20 1000
40 1000
50 1000
30 1000
1 1000
66

提示

制約

  • 1 < = D < = 10 1\ <\ =\ D\ <\ =\ 10
  • 1 < = pi < = 100 1\ <\ =\ p_i\ <\ =\ 100
  • 100 < = ci < = 106 100\ <\ =\ c_i\ <\ =\ 10^6
  • 100 < = G 100\ <\ =\ G
  • 入力中のすべての値は整数である。
  • ci, G c_i,\ G はすべて 100 100 の倍数である。
  • 総合スコアを G G 点以上にすることは可能である。

Sample Explanation 1

この場合、AtCode には 100 100 点を付けられた問題が 3 3 問、200 200 点を付けられた問題が 5 5 問あります。100 100 点の 3 3 問をすべて解いた際のコンプリートボーナスは 500 500 点、200 200 点の 5 5 問をすべて解いた際のコンプリートボーナスは 800 800 点です。高橋くんの目標は総合スコアを 700 700 点以上にすることです。 目標を達成する方法の一つは、200 200 点問題を 4 4 問解いて 800 800 点の基本スコアを得ることです。しかし、100 100 点問題を 3 3 問すべて解くと、基本スコア 300 300 点に加えてコンプリートボーナスの 500 500 点が与えられて総合スコアが 800 800 点となり、より少ない問題数で目標を達成することができます。

Sample Explanation 2

入力例 1 と似たケースですが、今回の高橋くんの目標は 2000 2000 点以上です。この場合、200 200 点の 5 5 問は必ずすべて解かなければならず、さらに 100 100 点問題を 2 2 問解くことで総合スコアが 2000 2000 点となります。

Sample Explanation 3

ふたたび入力例 1 と似たケースですが、今回の高橋くんの目標は 400 400 点以上です。この場合、200 200 点問題を 2 2 問解くだけで目標を達成できます。

Sample Explanation 4

500 500 点の問題が 1 1 問しか存在しませんが、このような場合でもその問題を解くことでコンプリートボーナスが与えられます。