問題

JOI 高校の授業には，太郎君，次郎君，三郎君，四郎君，花子さんの 5 人の生徒が参加した．

この授業では，期末試験を実施した．期末試験は，5 人全員が受験した．期末試験の点数が 40 点以上の生徒は，期末試験の点数がそのまま成績になった．期末試験の点数が 40 点未満の生徒は全員，補習を受け，成績が 40 点になった．

5 人の生徒の期末試験の点数が与えられたとき，5 人の成績の平均点を計算するプログラムを作成せよ．

入力例 1

10
65
100
30
95

出力例 1

68

入出力例 1 では，太郎君と四郎君の期末試験の点数は 40 点未満なので，太郎君と四郎君の成績は 40 点になる．次郎君と三郎君と花子さんの期末試験の点数は 40 点以上なので，次郎君の成績は 65 点，三郎君の成績は 100 点，花子さんの成績は 95 点となる．5 人の成績の合計は 340 なので，平均点は 68 点となる．

入力例 2

40
95
0
95
50

出力例 2

64

問題

20XX 年に東京で世界的なスポーツ大会が開かれることになった．プログラミングコンテストはスポーツとして世界で楽しまれており，競技として採用される可能性がある．採用される競技を決める審査委員会について調べたところ，次のようなことが分かった．

• 審査委員会のために，候補となる N 個の競技を面白い方から順番に並べたリストが作成された．リストの上から i 番目には i 番目に面白い競技が書かれている．それを競技 i とする．さらに競技 i の開催に必要な費用 A_i が書かれている．
• また，審査委員会は委員 1 から委員 M までの M 人の委員で構成されている．委員 j は自分の審査基準 B_j をもっており，開催に必要な費用が B_j 以下の競技のうち最も面白いものに 1 票を投票した．
• どの委員の審査基準に対しても，少なくとも 1 つの競技は開催に必要な費用が審査基準以下であった．したがって，委員は全員 1 票を投票した．
• 最も多く票を獲得した競技は 1 つだけであった．

競技のリストと委員の情報が与えられたとき，最も多く票を獲得した競技の番号を求めるプログラムを作成せよ．

入力例 1

4 3
5
3
1
4
4
3
2

出力例 1

2

入出力例 1 では，競技は 4 つあり，委員は 3 人いる．リストの 4 つの競技にかかる費用はそれぞれ 5, 3, 1, 4 である．

• 委員 1 の審査基準は 4 である．費用が 4 以下の競技のうち最も面白いものは競技 2 である．
• 委員 2 の審査基準は 3 である．費用が 3 以下の競技のうち最も面白いものは競技 2 である．
• 委員 3 の審査基準は 2 である．費用が 2 以下の競技のうち最も面白いものは競技 3 である．

よって，競技 2 が 2 票，競技 3 が 1 票を獲得する．最も多く票を獲得した競技は競技 2 であるので，2 を出力する．

入力例 2

6 6
3
1
4
1
5
9
2
6
5
3
5
9

出力例 2

1

入出力例 2 では，競技 1 が 5 票，競技 2 が 1 票を獲得する．最も多く票を獲得した競技は競技 1 なので，1 を出力する．

問題

JOI 君は，IOI 国にある超都という都市の観光ツアーを計画することになった．

超都は，南北方向にまっすぐに伸びる W 本の道路と，東西方向にまっすぐに伸びる H 本の道路により，碁盤の目の形に区分けされている．

南北方向の W 本の道路には，西から順に 1, 2, \ldots, W の番号が付けられている．また，東西方向の H 本の道路には，南から順に 1, 2, \ldots, H の番号が付けられている．西から i 番目の南北方向の道路と，南から j 番目の東西方向の道路との交差点を (i, j) で表す．

さらに，下図のように，各交差点からは１つ北東の交差点への道がある（最も北の道路上の交差点と最も東の道路上の交差点を除く）．また，１つ南西の交差点への道もある（最も南の道路上の交差点と最も西の道路上の交差点を除く）．すなわち，交差点 (i, j) からは，もし交差点 (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1) があるときは，それらの交差点へ１本の道を使って行くことが出来る．それに加え，もし交差点 (i - 1, j - 1), (i + 1, j + 1) があるときは，それらの交差点へも１本の道を使って行くことが出来る．

JOI 君はツアーの計画として既に N 個の観光スポットをどのような順番で訪れるかを決めている．i 番目 (1 \leqq i \leqq N) に訪れる観光スポットは交差点 (X_i, Y_i) にある．JOI 君は，ツアーにかかる時間をできるだけ短くするために，通らなければならない道の本数を少なくしたい．観光スポットを事前に決めた順番で訪れるために通らなければならない道の本数の合計の最小値を求めるプログラムを作成せよ．

ただし，ツアーの開始地点は交差点 (X_1, Y_1) である．また，ツアーの途中で超都の外へ移動してはならないものとする．また，JOI 君は，観光スポットのある交差点を，観光スポットを訪れずに通過することもできる．

（予選競技実施後に追記） 「道の本数の合計」についての補足．ツアーの途中で同じ道を 2 回以上通ることもできる．その場合，「道の本数の合計」としては，その道については通った回数だけ重複して数えるものとする．

入力例 1

4 3 3
1 1
3 3
4 1

出力例 1

5

入出力例 1 では，例えば (1, 1), (2, 2), (3, 3), (3, 2), (4, 2), (4, 1) の順で交差点を訪れれば良い．

入力例 2

4 3 5
1 3
4 3
2 2
2 2
1 3

出力例 2

7

入出力例 2 のように，同じ交差点に複数回訪れることもある．

問題

IOI 高校のプログラミング部には，J 君と O 君と I 君の 3 人の部員がいる．プログラミング部では，部活のスケジュールを組もうとしている．

今，N 日間の活動のスケジュールを決めようとしている．各活動日のスケジュールとして考えられるものは，各部員については活動に参加するかどうかの 2 通りがあり，部としては全部で 8 通りある．部室の鍵はただ 1 つだけであり，最初は J 君が持っている．各活動日には，その日の活動に参加する部員のうちのいずれか 1 人が鍵を持っている必要があり，活動後に参加した部員のいずれかが鍵を持って帰る．

プログラミング部では，活動日には毎回必ず活動が行われるように，あらかじめ各活動日の責任者を定めた．責任者は，必ずその日の活動に出席しなければならない．

スケジュールを決めようとしている日数と，各活動日の責任者が誰であるかの情報が与えられた時，すべての活動日に部活動を行うことができるようなスケジュール表として考えられるものの数を 10\,007 で割った余りを求めるプログラムを作成せよ．ただし，部活の終了時に鍵を持って帰る部員は，その日の活動に参加している部員の誰でもよく，最終日は誰が鍵を持って帰ってもよいものとする．

入力例 1

2
OI

出力例 1

7

入出力例 1 において， 2 日間の活動日のスケジュールを考える．1 日目の責任者は O 君， 2 日目の責任者は I 君である．問題文の条件をみたすスケジュール表は 7 通り考えられる．

この表では，J，O，I はそれぞれその日に J 君，O 君，I 君が参加することを表す．1 日目の責任者は O 君であるが，最初鍵を持っているのは J 君であるため，1 日目の活動には J 君，O 君の両方が参加する必要があることに注意せよ．また，1 日目に鍵を持って帰った人は 2 日目にも参加しないといけないので，1 日目と 2 日目の両方に参加する人が少なくとも 1 人存在しなければならないことに注意せよ．

入力例 2

20
JIOIJOIJOJOIIIOJIOII

出力例 2

4976

入出力例 2 において，条件をみたすスケジュール表は全部で 72\,493\,594\,992 通り考えられる．それを 10\,007 で割った余りである 4\,976 を出力する．

問題

IOI 国は町 1 から町 N までの N 個の町からなり，町と町とは道路で結ばれている．IOI 国には K 本の道路があり，すべての道路は異なる 2 つの町を結んでいる．車は道路を双方向に自由に移動できるが，道路以外を通ってある町から別の町に行くことはできない．

IOI 国の町 1 に住む JOI 君は，町 N に住む祖母の家までタクシーで行くことにした．IOI 国にはタクシー会社 1 からタクシー会社 N までの N 個のタクシー会社がある．IOI 国のタクシー会社には次のような少々特殊な規則がある．

• タクシー会社 i のタクシーには，町 i でのみ乗車できる．
• タクシー会社 i のタクシーの運賃は，利用した距離によらず C_i である．
• タクシー会社 i のタクシーは，乗車してから連続して最大 R_i 本の道路しか通ることができない．

たとえば R_1 = 2 の場合，町 1 からタクシー会社 1 のタクシーに乗車すると，最大 2 本の道路しか通ることができないため，道路を 3 本以上通るためには途中の町でタクシーを乗り換える必要がある．

JOI 君は町以外の地点でタクシーに乗ったりタクシーから降りたりすることはできない．また，タクシー以外の移動手段を用いることもできない．JOI 君が町 N に到達するために必要な運賃の合計の最小値を求めるプログラムを作成せよ．

入力例 1

6 6
400 2
200 1
600 3
1000 1
300 5
700 4
1 2
2 3
3 6
4 6
1 5
2 4

出力例 1

700

上の入出力例は，以下の図に対応している．円は町を，線は道路を表す．

この入出力例で JOI 君が最小の運賃で町 6 に到達するには，以下のようにする．

町 1 からタクシーに乗って町 5 に行く．(運賃 400)
町 5 からタクシーに乗って町 6 に行く．(運賃 300)
JOI 君がこのようなルートを通った場合の運賃の合計は 400 + 300 = 700 であるので，700 を出力する．

問題

JOI 君はお昼ごはんに，中華料理屋で小籠包を食べることにした． 小籠包とは，具と熱いスープを小麦粉の皮で包んだ料理であり，食べるときにスープが周囲に飛び散ることで知られている．

JOI 君が注文した小籠包のセットは，具やスープの異なる N 個の小籠包からなる． N 個の小籠包は等間隔に一列に並んでおり，順番に 1 から N の番号がつけられている． i 番目の小籠包と j 番目の小籠包の間の距離は絶対値 |i - j| である．

JOI 君は小籠包をある順番で食べていく． 最初，すべての小籠包のおいしさは 0 である． i 番目の小籠包を食べると，周囲にその汁が飛び散り，まだ食べられていない小籠包のうち，小籠包 i からの距離が D_i 以下の小籠包に汁がかかる．汁がかかった小籠包はおいしさが A_i 増える．すなわち， i 番目の小籠包を食べたときに， j 番目の小籠包 (1 \leqq j \leqq N かつ i - D_i \leqq j \leqq i + D_i) がまだ食べられずに残っているならば， j 番目の小籠包のおいしさが A_i 増える．

JOI 君は，食べる順番を工夫することで，食べる小籠包のおいしさの合計を最大化したい． もっとも良い順番で食べたときの，JOI 君が食べる小籠包のおいしさの合計を求めるプログラムを作成せよ．

入力例 1

5
1 0 1 1 2
0 2 6 3 4

出力例 1

20

入出力例 1 では，5 番目 → 3 番目 → 1 番目 → 2 番目 → 4 番目 の順番で食べると，おいしさの合計が 20 になる．合計が 20 を超えるような食べ方は存在しないので，これが最善である．

入力例 2

10
5 2 7 2 6 5 3 5 3 6
8 7 8 4 0 6 0 10 10 0

出力例 2

237