Problem B War II

Time Limit : 1 sec, Memory Limit : 65536 KB

Problem B War II

第二次ProblemB大戦

R大学の2D好きの人たち (2DRespecters)は,A津大学で開催されるプログラミングの練習合宿に参加する. この練習合宿では,参加者たちが自作のプログラミング問題を持ち寄り,練習に用いる. 今年は,2DRespectersの面々は手軽に作問できるB問題の作問担当者に立候補したため,B問題担当者の座を争うことになった.

戦いの舞台は,とある自販機である. この自販機は,90円のジュースを1種類だけ販売しており,お手頃価格で購入できることで有名である. ただし,自販機には,10円玉と100円玉の2つの硬貨しか投入することができず,釣銭もこれらの硬貨でしか支払われない.

自販機の内部には,10円玉を保存するための10円玉ストレージと,100円玉を保存するための100円玉ストレージが備え付けられており,それぞれには,始めにT枚の10円玉とH枚の100円玉が保存されている. 自販機には,硬貨を一度に一枚しか投入できず,投入された硬貨は,硬貨に対応する内部のストレージに保存される. 自販機の残金表示は,始め0円になっており,硬貨を投入すると,投入した硬貨の金額分,自販機の残金が増加する. 硬貨を投入した結果,自販機の残金が,90円以上になったならば,1本の缶ジュースがジュースの取り出し口に出てくると同時に,自販機の残金から90円を引いた額とちょうど同じ額の硬貨が釣銭として釣銭の取り出し口に出てくる. このときの釣銭は,内部のストレージにある硬貨で払える範囲で,できるだけ多くの10円玉を用いて支払われる. 釣銭が支払われた後,自販機の残金は0円に戻る.

ただし,この自販機は次の操作を行うと壊れる.

  • 釣銭を払えなくなったとき
  • 10円玉ストレージの保存可能枚数の上限であるL枚を超える10円玉が保存されようとしたとき

自販機の紹介が終わったので,N人の2DRespectersのメンバーが参加したゲームについて説明する. ゲームの開始時には,2DRespectersのメンバーiはそれぞれ10円玉ti枚と100円玉をhi枚ずつ持っている. このゲームでは,N人全員が順番に1枚ずつ硬貨を自販機に投入していく. このとき,メンバー1,メンバー2,....,メンバーNの順で投入する. N人全員が1枚ずつ硬貨の投入を終えたら,前回と同じ順番で順番に1枚ずつ硬貨の投入を行い,3週目以降も同様である. 硬貨の投入は,10円玉を持っている場合は必ず10円玉を投入し,10円玉を持っていない場合は100円玉を投入するものとする. メンバーiが硬貨を投入したとき,釣銭の取り出し口に釣銭が出てきた場合は,その全ての釣銭をメンバーiが受け取り,取り出し口に何もない状態にしてから,次のメンバーのターンに移る.

このゲームは,次の条件を最初に満たしたメンバーが勝者となり,B問題の作問担当者となる.

  • 自販機を壊したとき
  • 自分の順番に,硬貨を1枚も持っていないとき

なお,自販機には無限にジュースが保存されており,100円玉ストレージには無限に100円玉を保存することができる.

あなたの仕事は,B問題担当者が誰になったかを求めるものである.

なけなしの硬貨を犠牲に,B問題を賭けた壮絶な戦いが??今,始まる. ちなみに,購入したジュースはちゃんとB問題担当者が後でおいしくいただきます.

Input

入力は,次の形式で与えられる.

N T H L
t1 h1
t2 h2
...
tN hN

Nは2DRespectersの人数であり,1 <= N <= 100である. THはそれぞれ,10円玉ストレージと100円玉ストレージに最初に保存されている硬貨の枚数であり,0 <= T, H <= 100である. Lは10円玉ストレージの保存可能枚数の上限であり,T <= L <= 100である. 1 <= i <= Nのとき,tiは,2DRespectersのメンバーiの10円玉の所持枚数を表し,hiは100円玉の所持枚数を表す.0 <= ti, hi <= 100である.

Output

B問題担当者になったメンバーの番号を1行に出力せよ.

Sample Input 1

3 0 0 100
4 0
3 0
3 0

Sample Output 1

2

Sample Input 2

3 0 0 8
4 0
3 0
3 0

Sample Output 2

3

Sample Input 3

3 0 0 100
2 1
3 0
3 0

Sample Output 3

1

Source: Aizu Competitive Programming Camp 2012 , Day 1, Aizu-Wakamatsu, Japan, 2012-09-03
Problem Setter:  THE 2DM@STER(@Respect2D, @slip0110, @_shnyh) ,  @kioa341, @utisam