情報オリンピック日本委員会では，台湾大会に向かう選手を応援するために新しい JOI 旗を作成することにした．

JOI 旗は，正方形が縦に M 行，横に N 列並んだ形をしており，各正方形には J，O，I のいずれかの文字が 1 つずつ書かれている．

JOI 旗の例

情報オリンピック日本委員会は JOI 旗とは別に JOI 紋章というものを決めている．JOI 紋章は，正方形が縦に 2 行，横に 2 列並んだ形をしており，各正方形には J，O，I のいずれかの文字が 1 つずつ書かれている．

JOI 紋章の例

JOI 旗に含まれる JOI 紋章の個数とは，JOI 旗に含まれる縦 2 行，横 2 列の領域のうち，その領域の J，O，I の配置が JOI 紋章と (回転や裏返しをせずに) 一致しているものの個数のことである．条件を満たす縦 2 行，横 2 列の領域同士が重なっていてもそれらを別々に数えるものとする．

情報オリンピック日本委員会は古い JOI 旗と 1 枚の白紙を持っている．白紙は JOI 旗を構成する正方形 1 個分の大きさで，J，O，I のうち好きな 1 文字を書き込むことができる．情報オリンピック日本委員会は以下のいずれか 1 つの操作をして，新しい JOI 旗を作成することにした．

• 古い JOI 旗に対して何も操作せず，そのまま新しい JOI 旗とする．白紙は使用しない．
• 白紙に 1 文字書き込み，古い JOI 旗のいずれかの正方形に重ねて貼り付けることで古い JOI 旗のうち 1 箇所を変更する．変更後の JOI 旗を新しい JOI 旗とする．

情報オリンピック日本委員会は新しい JOI 旗に含まれる JOI 紋章の個数をできるだけ多くしたいと思っている．あなたは新しい JOI 旗に含まれる JOI 紋章の個数の最大値を求めることになった．

課題

古い JOI 旗と JOI 紋章の情報が与えられたとき，新しい JOI 旗に含まれる JOI 紋章の個数の最大値を求めるプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 2 \leqq M \leqq 1\,000．
• 2 \leqq N \leqq 1\,000．

小課題

小課題 1 [30 点]

以下の条件を満たす．

• M \leqq 50．
• N \leqq 50．

小課題 2 [70 点]

追加の制限はない．

入力例 1

3 5
JOIJO
IJOOO
IIJIJ
JO
IJ

出力例 1

3

古い JOI 旗と JOI 紋章は問題文中の例の通りである．上から 2 行目，左から 4 列目の正方形を白紙を用いて J に変更すると，次のような形になる．

JOI 旗の 1 箇所を変更した例

このように変更した後の JOI 旗には次に示す 3 箇所に JOI 紋章と同じ配置の領域がある．

JOI 紋章と同じ配置の領域

JOI 紋章と同じ配置の領域が 4 箇所以上となる新しい JOI 旗は存在しないので，新しい JOI 旗に含まれる JOI 紋章の個数の最大値は 3 である．

入力例 2

2 6
JOJOJO
OJOJOJ
OJ
JO

出力例 2

2

白紙を使用しなくても最大値が得られる場合があることに注意せよ．

入力例 3

2 2
JI
IJ
JJ
JJ

出力例 3

0

この入出力例の場合，考えられるどの新しい JOI 旗においても，JOI 紋章が 1 つも含まれない．

Incredible Okashi Inc. は「途方もなくおいしいお菓子 (incredible okashi)」を製作している会社である．ここでは略して IOI 社と呼ぶ．IOI 社は特製の IOI 饅頭を作ったので，それを販売することになった．IOI 社は M 種類の饅頭を 1 個ずつ作った．作られた M 個の饅頭はすべて同じ大きさであるが，ひとつひとつ異なる味なので価格は様々であり，i 番目 (1 \leqq i \leqq M) の饅頭の価格は P_i 円である．

ところで，あなたは Just Odd Inventions 社を知っているだろうか？ この会社の業務は「ただ奇妙な発明 (just odd inventions)」をすることである．ここでは略して JOI 社と呼ぶ．IOI 社は，饅頭を詰めるための高級な箱を JOI 社に発注することになった．JOI 社の製作する饅頭用の箱は N 種類あり，j 番目 (1 \leqq j \leqq N) の箱は最大で C_j 個の饅頭を詰められる大きさであり，販売価格は E_j 円である．これらの N 種類の箱のうちの何種類か (0 種類以上 N 種類以下) を 1 個ずつ発注し，饅頭をそれらの箱に詰め分けてセットで販売することになった．各饅頭セットの価格は，それに含まれる饅頭の価格の合計である．

すべての饅頭セットが売れるとした場合，IOI 社が得ることができる利益の最大値はいくらだろうか．ここで利益とは，販売した饅頭セットの価格の合計から，発注した箱の価格の合計を引いた値である．なお，箱に詰めなかった饅頭については，IOI 社のスタッフがおいしくいただくため，利益には影響しないものとする．

課題

各饅頭の価格と，各箱の大きさと価格が与えられたとき，IOI 社が得ることができる利益の最大値を求めるプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 1 \leqq M \leqq 10\,000．
• 1 \leqq N \leqq 500．
• 1 \leqq P_i \leqq 10\,000 (1 \leqq i \leqq M)．
• 1 \leqq C_j \leqq 10\,000 (1 \leqq j \leqq N)．
• 1 \leqq E_j \leqq 10\,000 (1 \leqq j \leqq N)．

小課題

小課題 1 [25 点]

N \leqq 10 を満たす．

小課題 2 [35 点]

C_j \leqq 10 (1 \leqq j \leqq N) を満たす．

小課題 3 [40 点]

追加の制限はない．

入力例 1

4 3
180
160
170
190
2 100
3 120
4 250

出力例 1

480

この例では，1 番目の箱 (100 円) と 2 番目の箱 (120 円) を発注し，たとえば 1 番目の箱に 1 番目の饅頭と 2 番目の饅頭を詰めて 180 + 160 = 340 円のセットとして販売，2 番目の箱に 3 番目の饅頭と 4 番目の饅頭を詰めて 170 + 190 = 360 円のセットとして販売すると，IOI 社の利益は 700 - 220 = 480 円となる．

入力例 2

2 2
1000
2000
1 6666
1 7777

出力例 2

0

入力例 3

10 4
200
250
300
300
350
400
500
300
250
200
3 1400
2 500
2 600
1 900

出力例 3

450

JOI 君は妹の JOI 子ちゃんと JOI 美ちゃんと一緒におやつを食べようとしている．今日のおやつは 3 人の大好物のバームクーヘンだ．

バームクーヘンは下図のような円筒形のお菓子である．3 人に分けるために，JOI 君は半径方向に刃を 3 回入れて，これを 3 つのピースに切り分けなければならない．ただしこのバームクーヘンは本物の木材のように固いので，刃を入れるのは簡単ではない．そのためこのバームクーヘンにはあらかじめ N 個の切れ込みが入っており，JOI 君は切れ込みのある位置でのみ切ることができる．切れ込みに 1 から N まで時計回りに番号をふったとき，1 \leqq i \leqq N - 1 に対し，i 番目の切れ込みと i + 1 番目の切れ込みの間の部分の大きさは A_i である．また N 番目の切れ込みと 1 番目の切れ込みの間の部分の大きさは A_N である．

図 1: バームクーヘンの例 N = 6，A_1 = 1，A_2 = 5，A_3 = 4，A_4 = 5，A_5 = 2，A_6 = 4

妹思いの JOI 君は，バームクーヘンを 3 つのピースに切り分けたあと，自分は最も小さいピースを選び，残りの 2 つのピースを 2 人の妹にあげることにした．一方で，JOI 君はバームクーヘンが大好物なので，できるだけたくさん食べたいと思っている．最も小さいピースの大きさが最大になるように切ったとき，JOI 君が食べることになるピースの大きさはいくらになるだろうか．

課題

切れ込みの個数 N と，各部分の大きさを表す整数 A_1, \ldots, A_N が与えられる．バームクーヘンを 3 つに切り分けたときの，最も小さいピースの大きさの最大値を出力するプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 3 \leqq N \leqq 100\,000．
• 1 \leqq Ai \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．

小課題

小課題 1 [5 点]

N \leqq 100 を満たす．

小課題 2 [15 点]

N \leqq 400 を満たす．

小課題 3 [30 点]

N \leqq 8\,000 を満たす．

小課題 4 [50 点]

追加の制限はない．

入力例 1

6
1
5
4
5
2
4

出力例 1

6

図 2: 1 番目の切れ込みと 3 番目の切れ込みと 5 番目の切れ込みで切るのが最善である．

入力例 2

30
1
34
44
13
30
1
9
3
7
7
20
12
2
44
6
9
44
31
17
20
33
18
48
23
19
31
24
50
43
15

出力例 2

213

フクロモモンガの JOI 君が住んでいる森にはユーカリの木が N 本生えており，それらの木には 1 から N の番号がついている．木 i の高さは H_i メートルである．

JOI 君が相互に直接飛び移ることのできる木の組が M 組あり，各組の木の間を飛び移るためにかかる時間が定まっている．JOI 君が木の間を飛び移っている間は，地面からの高さが 1 秒あたり 1 メートル下がる．すなわち，JOI 君の現在の地面からの高さが h メートル，木の間を飛び移るためにかかる時間が t 秒であるとき，飛び移った後の地面からの高さは h - t メートルとなる．ただし，h - t が 0 よりも小さくなる場合や行き先の木の高さよりも大きくなる場合は飛び移ることができない．

さらに，JOI 君は木の側面を上下に移動することによって，地面からの高さを 0 メートルから今いる木の高さの範囲で増減させることができる．JOI 君が地面からの高さを 1 メートル増加または減少させるためには 1 秒の時間がかかる．

JOI 君は，木 1 の高さ X メートルの位置から木 N の頂上 (高さ H_N メートルの位置) に行こうとしており，そのためにかかる時間の最小値を知りたい．

課題

各木の高さと，JOI 君が直接飛び移ることができる木の組の情報と，最初 JOI 君がいる場所の高さが与えられる．木 N の頂上に行くためにかかる時間の最小値を求めるプログラムを作成せよ.

制限

すべての入力データは以下の条件を満たす．

• 2 \leqq N \leqq 100\,000．
• 1 \leqq M \leqq 300\,000．
• 1 \leqq H_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．
• 1 \leqq T_j \leqq 1\,000\,000\,000 (1 \leqq j \leqq M)．
• 0 \leqq X \leqq H_1．

小課題

小課題 1 [25 点]

以下の条件を満たす．

• N \leqq 1\,000．
• M \leqq 3\,000．
• H_i \leqq 100 (1 \leqq i \leqq N)．
• T_j \leqq 100 (1 \leqq j \leqq M)．

小課題 2 [25 点]

以下の条件を満たす．

• X = 0．

小課題 3 [50 点]

追加の制限はない．

入力例 1

5 5 0
50
100
25
30
10
1 2 10
2 5 50
2 4 20
4 3 1
5 4 20

出力例 1

110

例えば，以下のように移動すればよい．

1. 木 1 を 50 メートル登る．
2. 木 1 から木 2 に飛び移る．
3. 木 2 から木 4 に飛び移る．
4. 木 4 から木 5 に飛び移る．
5. 木 5 を 10 メートル登る．

入力例 2

2 1 0
1
1
1 2 100

出力例 2

-1

JOI 君は木 1 から木 2 に飛び移ることができない．

入力例 3

4 3 30
50
10
20
50
1 2 10
2 3 10
3 4 10

出力例 3

100

JOI 君はペーパークラフトが趣味である．今日も JOI 君はペーパークラフトの作品を作ろうとしている．

まず，JOI 君は設計図にしたがって 1 枚の長方形の紙に N 本の切り取り線を印刷した．各切り取り線は，紙の縦または横の辺に平行な線分である．紙を切り出してできるすべての部分は作品の中で何らかの部品として用いられる．当然のことながら，部品数の多い作品は製作が大変である．JOI 君は，すべての切り取り線にしたがって紙を切り出したとき，紙がいくつの部分に分かれるかを知りたい．

課題

紙の大きさと，N 本の切り取り線の情報が与えられる．これらの切り取り線にしたがって紙を切り分けたとき，紙がいくつの部分に分かれるかを求めるプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 1 \leqq W \leqq 1\,000\,000\,000．
• 1 \leqq H \leqq 1\,000\,000\,000．
• 1 \leqq N \leqq 100\,000．

小課題

小課題 1 [5 点]

以下の条件を満たす．

• W \leqq 1\,000．
• H \leqq 1\,000．
• N \leqq 1\,000．

小課題 2 [5 点]

以下の条件を満たす．

• N \leqq 1\,000．

小課題 3 [20 点]

共有点を持つような異なる 2 つの切り取り線の組の個数は，100\,000 以下である．

小課題 4 [20 点]

切り取り線上の任意の点から紙のある辺上の点まで，いくつかの切り取り線をたどって行くことができる．

小課題 5 [50 点]

追加の制限はない．

入力例 1

10 10 5
6 0 6 7
0 6 7 6
2 3 9 3
2 3 2 10
1 9 8 9

出力例 1

4

この入力の場合，切り取り線は下図のようになる．

よって，切り取り線によって紙は 4 つの部分に分かれる．なお，この入力は小課題 4 の条件を満たしている．

入力例 2

13 7 28
1 1 4 1
1 1 1 3
2 2 3 2
2 2 2 3
1 3 2 3
3 2 3 6
4 1 4 6
3 6 4 6
5 1 8 1
5 1 5 6
6 2 7 2
6 2 6 5
7 2 7 5
6 5 7 5
8 1 8 6
5 6 8 6
9 1 12 1
9 1 9 2
9 2 10 2
12 1 12 2
11 2 12 2
10 2 10 5
9 5 10 5
9 5 9 6
11 2 11 5
11 5 12 5
12 5 12 6
9 6 12 6

出力例 2

5

この入力の場合，切り取り線は下図のようになる．

よって，切り取り線によって紙は 5 つの部分に分かれる．なお，この入力は小課題 4 の条件を満たしていない．