0578 - 魔女っ娘ヒナくるん -Magic.49

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / Writer root / x 4 / 統計 /


TLE
1sec
MLE
64MB
得点
100

Magic.49 『Miracle VS Hinakurun』

前回までのあらすじ

ニトゥーリとの心理戦を物理で攻略し、

パルスィ姫を取り戻したヒナくるん!!

ついに事件の黒幕との決戦に挑む!!

本編

ヒナくるん

「・・・ついに来たわよ!!

覚悟しなさい!! "コティーヤ"!!」

コティーヤ

「よくここまで来ましたね。

奇跡的だと言えるでしょう。

ですがその奇跡もここまでです。

なぜなら、私は奇跡を司るのですから!!」

ヒナくるん

「笑わせないで!!

そんな奇跡、私たちの力には敵わないと言うことを

じっくりと味わわせてあげるわ!!」

問題

ついに戦いは、最終局面を迎えようとしている。

ヒナくるんは、攻撃方法をいくつか持っている。

各攻撃方法は、コティーヤに与えることができるダメージを持っている。

ダメージが p の攻撃を行うと、コティーヤの体力は p 減少する。

コティーヤの体力が 0 以下になったとき、ヒナくるんの勝利である。

ヒナくるんは、いくつかの攻撃を同時に行える。

各攻撃方法には番号が割り振られており、ヒナくるんは隣り合った番号の攻撃しか同時に行えない。

・攻撃1と攻撃2は同時に行えるが、攻撃1と攻撃3は番号が離れているため同時に行えない。

 攻撃1と攻撃2と攻撃3であれば、番号は隣り合っているため同時に行うことが出来る。

ヒナくるんが1ターンに行う攻撃の数は、全てのターンで統一されている。

・1ターン目に二つの攻撃を行った場合、2ターン目以降はヒナくるんは全て二つの攻撃を行う。

・つまり、1ターン目に二つの攻撃を行い、2ターン目に一つの攻撃を行うことは不可能である。

コティーヤは、奇跡により時々ヒナくるんの特定の攻撃によって受けるダメージが変わる。

ヒナくるんは、できるだけ1ターンに行う攻撃の数を少なくしたい。

・1ターンに三つの攻撃を行ってコティーヤの体力を0に出来たとしても、

 1ターンに二つの攻撃を行ってコティーヤの体力を0に出来た場合は、

 ヒナくるんは、1ターンに二つの攻撃を行いたい。

入力形式

一行目に、ヒナくるんの攻撃方法の数 n , コティーヤの体力 h , 攻撃可能なターン数  l  が与えられる。

二行目から、一行に渡り、

ヒナくるんの各攻撃方法のコティーヤに与えるダメージ di が与えられる。

次の行には、コティーヤの奇跡によりヒナくるんの攻撃方法のダメージが変更されてしまう回数 m が与えられる。

次の行から、m行に渡り、

ダメージが変更されてしまう攻撃方法 ai , 変更後のダメージ si , 変更されるターン ti が与えられる。

出力形式

ヒナくるんが l ターン以内にコティーヤに勝利することができれば、

ヒナくるんがコティーヤに勝利できる1ターンにおける最小の選択する攻撃方法の数を、

どうやっても負けてしまう場合は "Broadcasting accident" を出力せよ。

制約

  • 1 <= n <= 10000
  • 1 <= a <= n
  • 1 <= h <= 230
  • 1 <= l,m <= 100
  • 1 <= ti <= l
  • 0 <= di,si <= 100

入出力例

Sample Input Ⅰ

5 40 4
2 3 4 8 2
2
2 4 1
4 1 3

Sample Output Ⅰ

2

この例では、一ターン目と二ターン目に攻撃方法三と四、

三ターン目と四ターン目に攻撃方法二と三を選ぶことによって、

合計ダメージが40丁度となり、答は2となる。

参考までに、Sample Input Ⅰの

各ターンごとの各攻撃の与ダメージを示す。

Turn 1: 2 4 4 8 2  (攻撃方法2のダメージが4に変更される)
Turn 2: 2 4 4 8 2
Turn 3: 2 4 4 1 2  (攻撃方法4のダメージが1に変更される)
Turn 4: 2 4 4 1 2

Sample Input Ⅱ

3 89 5
8 9 1
1
2 7 5

Sample Output Ⅱ

Broadcasting accident

この例では、全ての攻撃方法を選んだとしても、

合計ダメージは88になり、コティーヤの体力に届かないため、

"Broadcasting accident"を出力する。