あなたを乗せた超時空移民船は長旅の末，ついに居住可能と思われる惑星を発見した．JOI 星と名付けられたその惑星は，その名の通り「ジャングル (Jungle)」，「海 (Ocean)」，「氷 (Ice)」の 3 種類の地形が入り組んだ過酷な惑星である．簡単な調査により，居住予定地近辺の地図が作成された．

居住予定地は南北 M km，東西 N km の長方形の形をしており，1 km 四方の正方形の区画に分けられている．区画は全部で MN 個あり，北から p 行目，西から q 列目の区画を (p, q) で表す．北西の角の区画が (1, 1) であり，南東の角の区画が (M, N) である．各区画の地形は，「ジャングル」，「海」，「氷」のいずれかであり，「ジャングル」は J，「海」は O，「氷」は I の英字 1 文字で表される.

さて，詳細な移住計画を立てるにあたり，K 箇所の長方形領域内に「ジャングル」，「海」，「氷」がそれぞれ何区画含まれるかを調べることにした．

課題

居住予定地の情報と，調査対象となる領域の情報が与えられたとき，それぞれの領域について，「ジャングル」，「海」，「氷」が何区画含まれているかを求めるプログラムを作成せよ．

制限

採点基準

採点用データのうち，配点の 30 %分については，M \leqq 50 かつ K \leqq 100 を満たす．配点の 50 %分については，M \leqq 50 を満たす．

入力例 1

4 7
4
JIOJOIJ
IOJOIJO
JOIJOOI
OOJJIJO
3 5 4 7
2 2 3 6
2 2 2 2
1 1 4 7

出力例 1

1 3 2
3 5 2
0 1 0
10 11 7

この入力例では， 2 番目の領域は上図のように「ジャングル」を 3 区画，「海」を 5 区画，「氷」を 2 区画含む．

あなたの町には JOI 古本店という老舗の古本屋があり，あなたは JOI 古本店をよく利用している．それぞれの本には基準価格が定まっており，JOI 古本店に行けばその価格で買い取ってもらえる．

JOI 古本店では，本を小説・漫画・雑誌など 10 種類のジャンルに分類して扱っている．ジャンルには 1 から 10 までの番号が付けられている．JOI 古本店には，同じジャンルの本をまとめて買い取ってもらうと高値で買い取ってくれるというサービスがある．具体的には，同じジャンルの本をまとめて T 冊買い取ってもらう場合，そのジャンルの本の一冊あたりの買取価格が基準価格より T − 1 円高くなる．例えば，同じジャンルで基準価格 100 円，120 円，150 円の本をまとめて JOI 古本店に売ったとすると，買取価格はそれぞれ 102 円，122 円，152 円となる．

さて，あなたは一身上の都合で急遽引越しをすることになった．あなたは N 冊の本を持っているが，新しい住居にすべての本を持っていくことは困難なため，N 冊の本のうち K 冊を JOI 古本店に売ることにした．

課題

N 冊の本それぞれの基準価格とジャンルの番号が与えられるとき，合計買取価格の最大値を求めるプログラムを作成せよ．

制限

採点基準

採点用データのうち，

配点の 20 %分については，N\leqq 20 を満たす．

配点の 20 %分については，すべての本のジャンルは 1 または 2 である．

配点の 10 %分については，これら 2 つの条件の両方を満たす．

配点の 30 %分については，これら 2 つの条件の少なくとも一方を満たす．

入力例 1

7 4
14 1
13 2
12 3
14 2
8 2
16 3
11 2

出力例 1

60

この入力例では，2 番目，4 番目，6 番目，7 番目の 4 冊の本を売ったとき，ジャンル 2 の本の買取価格が 1 冊あたり 2 円高くなるので，これらの本の買取価格は以下のようになる．

よって合計買取価格は 15 + 16 + 16 + 13 = 60 円である．このとき合計買取価格は最大となる．

JOI 国には N 個の町があり，それらの間は M 本の双方向に通行可能な道路で結ばれている．K 個の町にはショッピングモールがあり，国民は道路を通ってそれらの町のいずれかに行き買い物をする．

家の場所によっては，買い物に行くために長い距離を移動する必要があり，それは非常に不便である．国王はこの実情を把握するため，ショッピングモールのある町までの最短距離が家の場所によってどれだけ長くなりうるのかを調べることにした．家は道路の途中に建てられることもあるので (入力例 1 の説明を参 照)，この調査は非常に大変である．そこで国王は，優秀なプログラマーであるあなたに，調査を行うプログラムの作成を依頼した．

課題

道路の情報とショッピングモールのある町の情報が与えられるとき，ショッピングモールのある町からもっとも遠い道路上の点 (端点も含む) までの距離を求めるプログラムを作成せよ．町の中を移動するのにかかる距離は無視してよい．

制限

採点基準

採点用データのうち，配点の 40 %分については，K = 1 を満たす．

入力例 1

3 3 1
1 2 1
2 3 1
3 1 1
1

出力例 1

2

入力例 1 は次のような町を表す．道路の長さはすべて 1 である．ショッピングモールは町 1 にしかない．

ショッピングモールのある町までもっとも遠い点は，町 2 と町 3 を結ぶ道路上の，町 2 から距離 0.5 の位置にある点であり，ショッピングモールのある町までの距離は 1.5 である．よって，それを四捨五入した値である 2 を出力する．

入力例 2

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

出力例 2

3

昨年末，サンタクロースは JOI 村の子供たちにクリスマスプレゼントを渡すのを忘れてしまった．そこで，お詫びの気持ちとして子供たちにチョコレートケーキを届けることにした．届けるべき日は明日に迫っているので，そろそろ移動計画を考えなければならない．

JOI 村は，南北方向にまっすぐに伸びる W 本の道路と，東西方向にまっすぐに伸びる H 本の道路により，碁盤の目の形に区分けされている. 南北方向の W 本の道路には，西から順に 1,2,\ldots,W の番号が付けられており，東西方向の H 本の道路には，南から順に 1,2,\ldots,H の番号が付けられている. 西から x 番目の南北方向の道路と，南から y 番目の東西方向の道路が交わる交差点を (x, y) で表す. JOI 村には N 軒の家があ り，それらはいずれかの交差点に位置している. サンタクロースは道路に沿ってのみ移動することができる. 隣り合う交差点の間を移動するのにかかる時間を 1 とする.

JOI 村のすべての家には子供がいるので，サンタクロースは JOI 村のすべての家に 1 個ずつチョコレートケーキを届けてまわらなければならない. 大切なチョコレートケーキを持ってトナカイと空を飛びまわるのはやや危険であるので，サンタクロースとトナカイは JOI 村のいずれかの交差点に降り立ち，サンタクロースがそこから歩いてチョコレートケーキを届けることにした. サンタクロースは同時に 2 個以上のチョコレートケーキを運んで歩くことはしない．つまり，サンタクロースはチョコレートケーキを 1 軒の家に届けるたびに降り立った交差点に戻る．

サンタクロースは，JOI 村に降り立ってからすべての家にチョコレートケーキを届けるまでの所要時間が最小になるような移動計画を選ぶことにした．ここで，最後の家にチョコレートケーキを届けてから降り立った交差点に戻るまでの時間は所要時間に含めないことに注意せよ．また，移動にかかる時間以外は考えない．

課題

家の位置の情報が与えられたとき，サンタクロースが降り立つ交差点をうまく選んだ場合の，JOI 村に降り立ってからすべての家にチョコレートケーキを届けるまでの所要時間の最小値と，所要時間を最小にするために降り立つべき交差点の位置を求めるプログラムを作成せよ．

制限

注意

この問題では，扱う整数の範囲が 32 ビットに収まらない可能性があることに注意せよ．

採点基準

採点用データのうち，配点の 40 %分については，N \leqq 1\,000 を満たす．

採点用データのうち，配点の 10 %分については，W\leqq 50,H\leqq 50,N\leqq 1\,000 を満たす．

入力例 1

5 4
3
1 1
3 4
5 3

出力例 1

10
3 3

たとえば，次のような移動計画により所要時間を最小にできる．

• 交差点 (3, 3) に降り立つ．
• 交差点 (3, 4) に位置している家にチョコレートケーキを届ける．ここまでの経過時間は 1 である．
• 交差点 (3, 3) に戻る．ここまでの経過時間は 2 である．
• 交差点 (5, 3) に位置している家にチョコレートケーキを届ける．ここまでの経過時間は 4 である．
• 交差点 (3, 3) に戻る．ここまでの経過時間は 6 である．
• 交差点 (1, 1) に位置している家にチョコレートケーキを届ける．ここまでの経過時間は 10 である．

入力例 2

4 6
8
1 3
3 2
4 4
2 5
2 3
3 3
3 4
2 4

出力例 2

21
2 3

家がある交差点に降り立ってもよいことに注意せよ．

あなたは Just Odd Inventions 社を知っているだろうか? この会社の業務は「ただ奇妙な発明 (just odd inventions)」をすることである．ここでは略して JOI 社と呼ぶ．

JOI 社では多くの微生物を 1 つのシャーレに生きたまま閉じ込める研究をしている．調査対象の微生物は N 匹存在し，1,2,\ldots,N という番号がついている．各微生物はシャーレに閉じ込められると，foo (fatally odd object) と呼ばれる有害物質を一瞬のうちにシャーレ内に放出する．各微生物が放出する foo の量は知られている．シャーレに閉じ込められた全微生物が放出した foo はシャーレ内の各微生物が均等に摂取する．各微生物の foo 許容量は知られており，この量を超えて foo を摂取すると微生物は死んでしまう．

微生物 i の foo 放出量は a_i ミリグラム，foo 許容量は b_i ミリグラムである．すなわち，シャーレに微生物 i_1,i_2,\ldots,i_k を閉じ込めたとき，シャーレ内の各微生物はそれぞれ \displaystyle \frac{a_{i_1}+a_{i_2}+\cdots+a_{i_k}}k ミリグラムの foo を摂取し，シャーレ内の微生物 i は，この摂取量が b_i より大きいと死んでしまう．

JOI 社からの委託により，あなたは出来るだけ多くの微生物をシャーレに生きたまま閉じ込めなければならない．ただし，微生物の死骸はシャーレ内の環境に悪影響を及ぼすため，シャーレ内のどの微生物も foo の摂取で死んではならない．

なお，JOI 社が「ただ奇妙な発明」をすることでどうやって利益を得ているかは，今もって謎であり，JOI 社内でも社長以外の誰も知らない．

課題

調査対象の微生物数と，各微生物の foo 放出量と foo 許容量が与えられたとき，1 つのシャーレに閉じ込めることができる微生物数の最大値を求めるプログラムを作成せよ．

制限

注意

この問題では，扱う整数の範囲が 32 ビットに収まらない可能性があることに注意せよ．

採点基準

採点用データのうち，配点の 30 %分については，N\leqq 1\,000 を満たす．

入力例 1

6
12 8
5 9
2 4
10 12
6 7
13 9

出力例 1

3

この例では，微生物 2, 4, 5 をシャーレに入れれば，放出される foo の合計量は 5 + 10 + 6 = 21 ミリグラムとなり，それぞれの微生物が摂取する foo の量は \displaystyle \frac{21}3=7 ミリグラムとなる．微生物 2, 4, 5 の foo 許容量はそれぞれ 9, 12, 7 ミリグラムなので，シャーレ内のどの微生物も死なない．また，4 匹以上の微生物をどの微生物も死なないようにシャーレに入れることはできない．