前回のラボライフ！ダイガクイン！！ マスターアイドルたちが競う最大の大会「ラボライフ」の前哨戦ともいえるイベント「マスターアイドルワールド」で9位を取ってしまったドサンコスノー。 キレのあるダンスは「9位の舞」、渾身の決めポーズも「9位の構え」などと冷やかされてしまい、心に深い傷を負ってしまう。 来たるラボライフ予備予選では絶対に9位をとるわけにはいかない…… 決意を新たにしたドサンコスノーは、自分たちの特技「セルフコントロール」に磨きをかけ、決戦の地へと向かうのだった。
N組のユニットが競う大会「ラボライフ」が開かれる。 この大会では、スマイル・ピュア・クールの3つの部門で別々に勝負が行われ、それぞれの勝負で得た得点の合計が高い順に総合順位が決定される。 スマイル部門の順位はそれぞれのユニットが持つスマイル値の値が高い順に決定される。 ピュア・クール部門でも同様にピュア値・クール値が高い順に順位が決定される。 順位に応じた得点設定は全部門で共通しており、ある部門でi位のユニットは、その部門ではr_i点を得る。
ここで、順位がi位のユニットと同じ値を持つユニットが複数ある場合、それらは同率i位とみなし、等しく得点r_iを得る。 より詳細には、kユニットが同率i位の場合には、kユニットが等しく得点r_iを得て、r_{i+1}からr_{i+k-1}までの得点を得るユニットはいない。 また、その次に値が大きいユニット (たち) は得点r_{i+k}を得る。 具体的な例として、例えばそれぞれスマイル値が1, 3, 2, 3, 2の5つのユニットがあり、順位が高い順に10, 8, 6, 4, 2点が得られる場合を考える。 このとき、2番目と4番目のユニットが10点、3番目と5番目のユニットが6点、1番目のユニットが2点を得ることになる。
ラボライフ予備予選に参加するユニット・ドサンコスノーは「ラボライフは遊びじゃない」と考えているため、真っ先に大会にエントリーし、1番目のユニットとなった。 しかし、大会に参加するN組すべてのスマイル値・ピュア値・クール値 (以降3値と呼ぶ) の情報を入手したところ、自分たちの総合順位が (同率) 9位であることがわかった。 ドサンコスノーは特技「セルフコントロール」により3値のうちいずれか1つの値を任意の値だけ上昇させることができるが、あまり上げすぎると疲れてしまい本戦に影響するので、できるだけ上昇値を小さくしたい。 ドサンコスノーはとにかく9位を脱したいので、同率8位以上になるようにセルフコントロールによって3値のいずれか1値を上げるとき、上げる必要のある最小の値を求めよ。
入力は以下の形式で与えられる。
N r_1 ... r_N s_1 p_1 c_1 ... s_N p_N c_N
1行目はユニットの数を表す整数Nが1行で与えられる。 続く2行目はN個の整数が空白区切りで与えられる。i (1 \leq i \leq N) 番目の整数は各部門で順位がi位だったときに貰える得点r_iを表す。 続くN行目のうち、j行目には3つの整数s_j, p_j, c_jが与えられる。これらはそれぞれj番目のユニットのスマイル値s_j、ピュア値p_j、クール値c_jを表す。 なおドサンコスノーは1番目のユニットであるとする。
セルフコントロールによって3値のどれかをxだけ上げることでドサンコスノーが同率8位以上になるような最小のxを1行に出力せよ。ただし、セルフコントロールによってどの値をどれだけ上げても順位が上げられない場合は "Saiko" と出力せよ。
9 9 8 7 6 5 4 3 2 1 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9
2
例えばセルフコントロールでスマイル値を2だけ上げると、ドサンコスノーの各部門における順位はそれぞれ同率7位、9位、9位となり、3+1+1 = 5点を得る。一方、2番目のユニットの各部門における順位はそれぞれ9位、8位、8位となり、1+2+2 = 5点を得る。他のユニットは6点以上を獲得するため、この2つのユニットが同率8位となり、条件を満たす。
9 9 8 7 6 5 4 3 2 1 1 1 1 2 6 9 6 9 2 9 2 6 3 5 8 5 8 3 8 3 5 4 7 4 7 4 7
Saiko
どの値をどれだけ上げてもドサンコスノーは11点までしか得ることができないが、他のユニットは必ず14点以上を得ることができるため、ドサンコスノーは不動の9位である。