問題

JOI 君が住んでいる地域には水道会社が X 社と Y 社の 2 つある．2 つの会社の 1 ヶ月の水道料金は，1 ヶ月の水道の使用量に応じて次のように決まる．

• X 社：1 リットル あたり A 円かかる．
• Y 社：基本料金は B 円である．使用量が C リットル以下ならば，料金は基本料金 B 円のみがかかる．使用量が C リットルを超えると基本料金 B 円に加えて追加料金がかかる．追加料金は使用量が C リットルを 1 リットル超えるごとに D 円である．

JOI 君の家では 1 ヶ月の水道の使用量が P リットルである．

水道料金ができるだけ安くなるように水道会社を選ぶとき，JOI 君の家の 1 ヶ月の水道料金を求めよ．

入力例 1

9
100
20
3
10

出力例 1

90

入出力例 1 では，JOI 君の家の 1 ヶ月の水道の使用量は 10 リットルである．

• X 社の水道料金は 9 \times 10 = 90 円である．
• JOI 君の家の 1 ヶ月の水道の使用量は 20 リットル以下なので，Y 社の水道料金は基本料金の 100 円である．

JOI 君の家は水道料金がより安い X 社を選ぶ．そのときの JOI 君の家の 1 ヶ月の水道料金は 90 円である．

入力例 2

8
300
100
10
250

出力例 2

1800

入出力例 2 では，JOI 君の家の 1 ヶ月の水道の使用量は 250 リットルである．

• X 社の水道料金は 8 \times 250 = 2\,000 円である．
• JOI 君の家の 1 ヶ月の水道の使用量は 100 リットル以上で，超過量は 250 - 100 = 150 リットルである．よって，Y 社の水道料金は基本料金の 300 円に加えて 10 \times 150 = 1\,500 円の追加料金がかかり，合計の水道料金は 3\,00 + 1\,500 = 1\,800 円である．

JOI 君の家は水道料金がより安い Y 社を選ぶ．そのときの JOI 君の家の 1 ヶ月の水道料金は 1\,800 円である．

問題

JOI 君は友達 1 から友達 N までの N 人の友達を招いてクリスマスパーティーを行った．クリスマスパーティーも盛り上がってきたところで，友達と一緒に次のようなゲームを行うことになった．

1. 最初に JOI 君は N 人の友達の中から 1 人を選ぶ．以降はその友達をターゲットと呼ぶことにする．
2. JOI 君は，ターゲットとして選んだ友達に，その人がターゲットであることをこっそり伝える．ターゲット以外の友達は，誰がターゲットかを知ることはできない．
3. ターゲット以外の友達はそれぞれ，ターゲットが誰かを予想して，その人の名前を紙に記入する．ターゲットは自分自身の名前を紙に記入する．
4. すべての人の記入が終わった後，JOI 君はターゲットの名前を発表する．
5. 予想が当たった人は 1 点を得る．なお，ターゲットは自分自身の名前を紙に記入しているので，必ず 1 点を得る．予想が外れた人には得点は与えられない．
6. それに加えて，予想が外れた人の人数を X 人としたとき，ターゲットは追加で X 点を得る．

JOI 君たちはこのゲームを M 回行った．それぞれの友達に対して，M 回のゲームにおける合計得点を求めよ．

入力例 1

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

出力例 1

3
4
5

入出力例 1 では 3 人の友達が 4 回のゲームを行う．

• 1 回目のゲームのターゲットは友達 1 であり，友達 1 は 2 点，友達 2 は 1 点，友達 3 は 0 点を得る．
• 2 回目のゲームのターゲットは友達 2 であり，友達 1 は 0 点，友達 2 は 2 点，友達 3 は 1 点を得る．
• 3 回目のゲームのターゲットは友達 3 であり，友達 1 は 0 点，友達 2 は 0 点，友達 3 は 3 点を得る．
• 4 回目のゲームのターゲットは友達 2 であり，友達 1 は 1 点，友達 2 は 1 点，友達 3 は 1 点を得る．

4 回のゲーム終了後の合計得点は，友達 1 は 3 点，友達 2 は 4 点，友達 3 は 5 点である．

入力例 2

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

出力例 2

3
1
6
3
2

問題

JOI 市は南北方向に H キロメートル，東西方向に W キロメートルの長方形の形をしており，H \times W 個の 1 キロメートル四方の小区画に区切られている．北から i 番目，西から j 番目の小区画を (i, j) と表す．

各小区画は上空に雲があるか雲がないかのどちらかである．すべての雲は，1 分経つごとに 1 キロメートル東に移動する．今日は実に天気が良いため，JOI 市の外から JOI 市内に雲が移動してくることはない．

今，各小区画の上空に雲があるかないかがわかっている．気象予報士であるあなたは，各小区画について，今から何分後に初めてその小区画の上空に雲が来るかを予測することになった．

各小区画について，今から何分後に初めてその小区画の上空に雲が来るか求めよ．

入力例 1

3 4
c..c
..c.
....

出力例 1

0 1 2 0
-1 -1 0 1
-1 -1 -1 -1

入出力例 1 では，JOI 市は 3 \times 4 個の小区画に区切られている．今の JOI 市の雲の状況は以下の通りである．図の上が北を表す．

この後，1 分ごとに雲は以下のように移動する．

入力例 2

6 8
.c......
........
.ccc..c.
....c...
..c.cc..
....c...

出力例 2

-1 0 1 2 3 4 5 6
-1 -1 -1 -1 -1 -1 -1 -1
-1 0 0 0 1 2 0 1
-1 -1 -1 -1 0 1 2 3
-1 -1 0 1 0 0 1 2
-1 -1 -1 -1 0 1 2 3

問題

現在カザフスタンがある地域には，古くは「シルクロード」と呼ばれる交易路があった．

シルクロード上には N + 1 個の都市があり，西から順に都市 0, 都市 1, \ldots, 都市 N と番号がつけられている．都市 i - 1 と都市 i の間の距離 (1 \leqq i \leqq N) は D_i である．

貿易商である JOI 君は，都市 0 から出発して，都市を順番に経由し，都市 N まで絹を運ぶことになった．都市 0 から都市 N まで M 日以内に移動しなければならない．JOI 君は，それぞれの日の行動として，以下の 2 つのうちいずれか 1 つを選ぶ．

• 移動：現在の都市から 1 つ東の都市へ 1 日かけて移動する．現在都市 i - 1 (1 \leqq i \leqq N) にいる場合は，都市 i に移動する．
• 待機：移動を行わず，現在いる都市で 1 日待機する．

移動は大変であり，移動するたびに疲労度が溜まっていく．シルクロードでは日毎に天候の変動があり，天候が悪い日ほど移動には苦労を要する．

JOI 君が絹を運ぶのに使える M 日間のうち j 日目 (1 \leqq j \leqq M) の天候の悪さは C_j であることが分かっている．都市 i - 1 から都市 i (1 \leqq i \leqq N) に j 日目 (1 \leqq j \leqq M) に移動する場合，疲労度が D_i \times C_j だけ溜まってしまう．移動を行わず待機している日は疲労度は溜まらない．

JOI 君は，それぞれの日の行動をうまく選ぶことで，できるだけ疲労度を溜めずに移動したい．JOI 君が M 日以内に都市 N に移動するときの，移動を開始してから終了するまでに溜まる疲労度の合計の最小値を求めよ．

入力例 1

3 5
10
25
15
50
30
15
40
30

出力例 1

1125

入出力例 1 において，溜まる疲労度の合計を最小にするように JOI 君が移動するには次のようにする．

• 1 日目は待機する．
• 2 日目に都市 0 から都市 1 へ移動する．このとき溜まる疲労度は 10 \times 30 = 300 である．
• 3 日目に都市 1 から都市 2 へ移動する．このとき溜まる疲労度は 25 \times 15 = 375 である．
• 4 日目は待機する．
• 5 日目に都市 2 から都市 3 へ移動する．このとき溜まる疲労度は 15 \times 30 = 450 である．

JOI 君がこのように移動した場合に溜まる疲労度の合計は 300 + 375 + 450 = 1\,125 である．これが最小値である．

入力例 2

2 6
99
20
490
612
515
131
931
1000

出力例 2

31589

問題

JOI 君は家族とともに海水浴に来た．さんざん泳いで泳ぎ疲れた JOI 君は，次は砂浜で砂の城を作って遊んだ．しばらくして砂遊びにも飽きると，JOI 君は城を放置してまた海に泳ぎに向かった．

JOI 君が作った城は，砂浜のうちのある長方形の領域に含まれている．この長方形の領域は，東西南北にマス目状に区切られている．各マスは，JOI 君が作った城の一部であるマス (以下，「城マス」と呼ぶ) かそうでないマス (以下，「更地マス」と呼ぶ) のいずれかである．それぞれの城マスには「強度」と呼ばれる 1 以上 9 以下の整数が定まっている．長方形の領域の外縁部，すなわち外側と接しているマスには城マスは存在しない．

やがて潮が満ちてきて，長方形の領域にも波が押し寄せてくるようになった．波が 1 つ押し寄せてくるたびに，城マスのうち次の条件を満たすものはすべて一斉に崩壊して，更地マスに変化する．

条件：周囲の 8 マス (東西南北および北東，北西，南東，南西方向に隣接するマス) にある更地マスの数が，そのマスの強度の値以上である． 波が引くと，まもなく次の波が押し寄せて来る．

十分多くの波が押し寄せると，城がすべて崩れてしまうか，丈夫な部分だけが残るかして，波が押し寄せてきても 1 つも城マスが崩壊しないような状態に落ち着く．1 つ以上の城マスを崩壊させるような波が押し寄せてくる回数を求めよ．

入力例 1

5 6
......
.939..
.3428.
.9393.
......

出力例 1

3

入出力例 1 においては，初めに押し寄せる波で強度 3 の城マスがすべて崩壊し，

......
.9.9..
..428.
.9.9..
......

という状態になる．

次に押し寄せてくる波では強度 2 の城マスが崩壊し，

......
.9.9..
..4.8.
.9.9..
......

という状態になる．

次に押し寄せてくる波では強度 4 の城マスが崩壊し，

......
.9.9..
....8.
.9.9..
......

という状態になる．

これ以降の波が城マスを崩すことはない．よって答えは 3 である．

入力例 2

10 10
..........
.99999999.
.9.323239.
.91444449.
.91444449.
.91444449.
.91444449.
.91232329.
.99999999.
..........

出力例 2

35

問題

盗賊の Anna と Bruno は大富豪の邸宅に忍び込み，財宝 1 から財宝 N までの N 個の財宝を見つけた．これらの財宝を Anna と Bruno で分配することになった．財宝のうちのいくつかを Anna が取り，残りの財宝のうちのいくつかを Bruno が取る．同じ財宝を 2 人が取ることはできない．Anna や Bruno は財宝を 1 個も取らなくてもよい．また，残った財宝は邸宅に残しておくので，2 人とも取らない財宝があってもよい．

それぞれの財宝には「市場価値」と「貴重度」という 2 つの値が定まっている．Anna が取った財宝の市場価値の合計と Bruno が取った財宝の市場価値の合計の差の絶対値が D 以下なら，Anna は公平だと思って満足する．一方，Bruno は，Anna より貴重度の大きい財宝が欲しいと思っている．

Anna が満足するように財宝を分配したときの，Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値の最大値を求めよ．

入力例 1

6 15
50 900
30 200
40 100
80 600
60 100
70 700

出力例 1

1200

入出力例 1 においては，Anna が財宝 2 と財宝 3 と財宝 5 を取り，Bruno が財宝 1 と財宝 6 を取ると，取った財宝の市場価値の合計は Anna が 130，Bruno が 120 となり，差の絶対値 10 が D = 15 以下なので Anna は満足する．このとき，取った財宝の貴重度の合計は Anna が 400，Bruno が 1\,600 となり，Bruno が取った財宝の貴重度の合計から Anna が取った財宝の貴重度の合計を引いた値は 1\,200 となる．これが最大である．

入力例 2

5 0
0 1000000000000000
0 1000000000000000
1 1
1000000000000000 0
1000000000000000 0

出力例 2

2000000000000000