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

Magic.49　『Miracle VS Hinakurun』

前回までのあらすじ

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

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

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

本編

ヒナくるん

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

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

コティーヤ

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

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

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

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

ヒナくるん

「笑わせないで！！

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

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

問題

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

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

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

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

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

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

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

・攻撃１と攻撃２は同時に行えるが、攻撃１と攻撃３は番号が離れているため同時に行えない。

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

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

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

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

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

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

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

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

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

入力形式

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

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

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

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

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

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

出力形式

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

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

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

制約

• 1 <= n <= 10000
• 1 <= a <= n
• 1 <= h <= 2³⁰
• 1 <= l,m <= 100
• 1 <= t_i <= l
• 0 <= d_i,s_i <= 100

入出力例

Sample Input Ⅰ

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

Sample Output Ⅰ

2

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

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

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

参考までに、Sample Input Ⅰの

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

Turn 1: 2 4 4 8 2　　（攻撃方法２のダメージが４に変更される）
Turn 2: 2 4 4 8 2
Turn 3: 2 4 4 1 2　　（攻撃方法４のダメージが１に変更される）
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"を出力する。