問題

JOI パスタ店では，ランチのおすすめパスタと搾りたてジュースのセットメニューが好評である．このセットメニューを注文するときは，その日の 3 種類のパスタと 2 種類のジュースから 1 つずつ選ぶ．パスタとジュースの値段の合計から 50 円を引いた金額が代金となる．

ある日のパスタとジュースの値段が与えられたとき，その日のセットメニューの代金の最小値を求めるプログラムを作成せよ．

入力例 1

800
700
900
198
330 

出力例 1

848

入出力例 1 では，2 つ目のパスタと 1 つ目のジュースを組み合わせた場合の 700 + 198 - 50 = 848 がその日のセットメニューの代金の最小値である．

入力例 2

1999
1999
100
189
100

出力例 2

150

入出力例 2 では，3 つ目のパスタと 2 つ目のジュースを組み合わせた場合の 100 + 100 - 50 = 150 がその日のセットメニューの代金の最小値である．

問題

JOI 国ではサッカーが人気であり，JOI リーグというリーグ戦が毎週行われている．

JOI リーグには N 個のチームが所属していて，1 から N までの番号がつけられている．すべての組み合わせの試合がちょうど一度ずつ行われる．つまり，N \times (N - 1) / 2 試合が行われる．各試合の勝敗はそれぞれのチームの得点で決まる．勝ったチームの勝ち点は 3 点であり，負けたチームの勝ち点は 0 点である．引き分けの場合，両チームの勝ち点は 1 点である．順位は各チームの獲得した勝ち点の合計で決定し，得失点差は考えない．勝ち点の合計が等しいチームの順位は上位に揃える．

例として，4 チームでのリーグ戦を考える．4 \times (4 - 1) / 2 = 6 試合が行われる．それらの結果が以下の表のようになったとする．ハイフンの左側はその横のチームの得点であり，右側はその縦のチームの得点である．

入力例 1

4
1 2 0 1
1 3 2 1
1 4 2 2
2 3 1 1
2 4 3 0
3 4 1 3

出力例 1

2
1
4
2

入出力例 1 は問題文中の例に対応している．

入力例 2

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

出力例 2

2
4
1
4
3

入出力例 2 における結果は以下の通りである．

問題

K 理事長は，JOI 市の中心部にある JOI ピザ店の常連客である．彼はある事情により，今月から節約生活を始めることにした．そこで彼は，JOI ピザ店で注文できるピザのうち，1 ドルあたりのカロリーが最大となるようなピザを注文したいと思った．このようなピザを「最高のピザ」と呼ぶことにしよう．「最高のピザ」は 1 種類とは限らない．

JOI ピザでは N 種類のトッピングから何種類かを自由に選び，基本の生地の上に載せたものを注文することができる．同種のトッピングを 2 つ以上載せることはできない．生地にトッピングを 1 種類も載せないピザも注文できる．生地の値段は A ドルであり，トッピングの値段はいずれも B ドルである．ピザの値段は，生地の値段と載せたトッピングの値段の合計である．すなわち，トッピングを k 種類 (0 \leqq k \leqq N) 載せたピザの値段は A + k \times B ドルである．ピザ全体のカロリーは，生地のカロリーと載せたトッピングのカロリーの合計である．

生地の値段とトッピングの値段，および，生地と各トッピングのカロリーの値が与えられたとき，「最高のピザ」の 1 ドルあたりのカロリー数を求めるプログラムを作成せよ．

入力例 1

3
12 2
200
50
300
100

出力例 1

37

入出力例 1 では，2 番目と 3 番目のトッピングを載せると，200 + 300 + 100 = 600 カロリーで 12 + 2 \times 2 = 16 ドルのピザになる． このピザは 1 ドルあたり 600 / 16 = 37.5 カロリーになる．これが「最高のピザ」となるので，37.5 の小数点以下を切り捨てた 37 を出力する．

入力例 2

4
20 3
900
300
100
400
1300

出力例 2

100

問題

あなたはパスタが大好物であり，毎日，晩御飯にパスタを作って食べている．あなたはトマトソース，クリームソース，バジルソースの 3 種類のパスタを作ることができる．

N 日間の晩御飯の予定を考えることにした．それぞれの日に 3 種類のパスタから 1 種類を選ぶ．ただし，同じパスタが続くと飽きてしまうので，3 日以上連続して同じパスタを選んではいけない．また，N 日のうちの K 日分のパスタはすでに決めてある．

入力として N の値と，K 日分のパスタの情報が与えられたとき，条件をみたす予定が何通りあるかを 10\,000 で割った余りを求めるプログラムを作成せよ．

入力例 1

5 3
3 1
1 1
4 2

出力例 1

6

入出力例 1 において，あなたは 5 日間の予定を考える．1 日目と 3 日目はトマトソースであり，4 日目はクリームソースである．また，3 日以上連続して同じパスタを選んではいけない．これらの条件をみたす予定は 6 通りある．

この表では，1 はトマトソースを，2 はクリームソースを，3 はバジルソースを表す．

入力例 2

20 5
10 2
4 3
12 1
13 2
9 1

出力例 2

2640

入出力例 2 において，条件をみたす予定は全部で 4\,112\,640 通りある．それを 10\,000 で割った余りである 2\,640 を出力する．

問題

JOI 社の建物は図のような 1 辺 1 メートルの正六角形をつなぎ合わせた形である．クリスマスが近づいているので，JOI 社では建物の壁面をイルミネーションで飾り付けることにした．ただし，外から見えない部分にイルミネーションを施すのは無駄なので，イルミネーションは外から建物の中を通らずに行くことのできる壁面にのみ飾り付けることにした．

JOI 社の建物の配置の例

上の図は上空から見た JOI 社の建物の配置の例である．正六角形内の数字は座標を表す．灰色の正六角形は建物がある場所を表し，白色の正六角形は建物がない場所を表す．この例では，赤の実線で示される部分がイルミネーションで飾り付けを行う壁面となり，その壁面の長さの合計は 64 メートルとなる．

JOI 社の建物の配置を表す地図が与えられたとき，飾り付けを行う壁面の長さの合計を求めるプログラムを作成せよ．ただし，地図の外側は自由に行き来できるものとし，隣接した建物の間は通ることはできないものとする．

入力例 1

8 4
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 0
1 0 1 0 1 1 1 1
0 1 1 0 1 0 1 0

出力例 1

64

入出力例 1 は問題文中の例に対応しており，イルミネーションで飾り付けを行う壁面の長さの合計は 64 メートルである．

入力例 2

8 5
0 1 1 1 0 1 1 1
0 1 0 0 1 1 0 0
1 0 0 1 1 1 1 1
0 1 0 1 1 0 1 0
0 1 1 0 1 1 0 0

出力例 2

56

問題

正の整数を (先頭に 0 をつけずに) 10 進法で書いて桁の数字を順番に見ていくと増加と減少を交互に繰り返しているとき，その数は「ジグザグ数」であると呼ぶことにしよう．たとえば，2947 は桁の数字が 2 → 9 → 4 → 7 と，増加 → 減少 → 増加 の順になっているのでジグザグ数である．また，71\,946 は 減少 → 増加 → 減少 → 増加 の順なのでジグザグ数である．一方，123 や 71\,446 や 71\,442 や 88 はジグザグ数ではない．なお，1 桁の正の整数はジグザグ数であると考えることとする．

A 以上 B 以下の M の倍数のうち，ジグザグ数の個数を 10\,000 で割った余りを求めるプログラムを作成せよ．

入力例 1

100
200
5

出力例 1

13

入出力例 1 において，100 以上 200 以下の 5 の倍数であるジグザグ数は，105, 120, 130, 140, 150, 160, 165, 170, 175, 180, 185, 190, 195 の 13 個である．

入力例 2

6
1234567
3

出力例 2

246

入出力例 2 において，6 以上 1\,234\,567 以下の 3 の倍数であるジグザグ数は 50\,246 個あるので，それを 10\,000 で割った余りである 246 を出力する．