問題

冬休みの宿題に毎回苦しめられてきた JOI 君が，今回は宿題を計画的に実行することにした．宿題は国語と算数のドリルであり，国語のドリルは A ページ，算数のドリルは B ページある．

JOI 君は，1 日に国語のドリルを最大 C ページと，算数のドリルを最大 D ページ進めることができるが，宿題をするとその日は遊ぶことができない．

冬休みは L 日あり，JOI 君は冬休み中に宿題を終わらせなければならない．JOI 君が冬休み中に最大で何日遊べるかを求めるプログラムを作成せよ．

入力例 1

20
25
30
6
8

出力例 1

15

入出力例 1 では，冬休みは 20 日間あり，国語のドリルが 25 ページ，算数のドリルが 30 ページある．JOI 君は 1 日に国語のドリルを最大 6 ページ，算数のドリルを最大 8 ページ進めることができる．例えば JOI 君が冬休み初日から国語のドリルを 6 ページ，算数のドリルを 8 ページずつ進めたとすると，国語のドリルを 5 日目に，算数のドリルを 4 日目に終わらせることができ，15 日間遊ぶことができる．これが JOI 君が冬休み中に遊べる日数の最大値なので，15 を出力する．

入力例 2

15
32
48
4
6

出力例 2

7

入出力例 2 では，例えば JOI 君が初日から国語のドリルを 4 ページ，算数のドリルを 6 ページずつ進めたとすると，8 日目に両方のドリルを終わらせることができ，7 日間遊ぶことができる．これが JOI 君が冬休み中に遊べる日数の最大値なので，7 を出力する．

問題

JOI 君は友達とゲームをすることにした．このゲームには N 人のプレイヤーが参加する．1 回のゲームのルールは次のようなものである：

それぞれのプレイヤーは 1 以上 100 以下の好きな整数をカードに書いて提出する．各プレイヤーは，自分と同じ数を書いた人が他にいなかった場合，自分の書いた数と同じ得点を得る．自分と同じ数を書いた人が他にいた場合は得点を得られない．

JOI 君たちはこのゲームを 3 回行った．各プレイヤーが 3 回のゲームにおいて書いた数が与えられたとき，各プレイヤーが 3 回のゲームで得た合計得点を求めるプログラムを作成せよ．

入力例 1

5
100 99 98
100 97 92
63 89 63
99 99 99
89 97 98

出力例 1

0
92
215
198
89

入力例 1 では，各プレイヤーが 3 回のゲームで得た得点の詳細は次のようになる：
プレイヤー 1：0 + 0 + 0 = 0
プレイヤー 2：0 + 0 + 92 = 92
プレイヤー 3：63 + 89 + 63 = 215
プレイヤー 4：99 + 0 + 99 = 198
プレイヤー 5：89 + 0 + 0 = 89

入力例 2

3
89 92 77
89 92 63
89 63 77

出力例 2

0
63
63

問題

JOI 君はお店の看板を作ることにした．

文字が等間隔に書かれた古い看板が N 枚ある．JOI 君は古い看板からいくつかの文字を消すことで看板を作る．残った文字列がお店の名前になっていて，しかも残った文字が等間隔に並んでいるようにしたい．看板は 1 枚の古い看板から作らなければならず，古い看板を切ったりつなげたりしてはならない．

お店の名前と N 枚の古い看板の情報が与えられた時，JOI 君が作ることができる看板の枚数を求めるプログラムを作成せよ．ただし，1 枚の古い看板から作ることができる看板が複数考えられる場合も，作ることができる看板は 1 枚であると考える．

入力例 1

4
bar
abracadabra
bear
bar
baraxbara

出力例 1

3

お店の名前は bar である．

1 枚目の古い看板には文字列 abracadabra が書かれている．この古い看板から 2 文字目，6 文字目，10 文字目以外を消すことで看板を作ることができる．

2 枚目は，2 文字目を消すと bar という文字列を作ることができるが，これは残った文字が等間隔に並んでいない．

3 枚目は，文字を何も消さなくても看板になっている．

4 枚目の古い看板から看板を作る方法は 2 通りある．1 つの方法は，1 文字目，2 文字目，3 文字目以外を消すことである．もう 1 つの方法は，6 文字目，7 文字目，8 文字目以外を消すことである．

よって，JOI 君は 1 枚目，3 枚目，4 枚目の古い看板から看板を作ることができるので，3 を出力する．

問題

日本が冬であるこの時期，南半球にあるオーストラリアでは暑い日が続いている．オーストラリアに住む IOI 君は，ある D 日間の天気予報をもとに，着る服の計画を立てることにした．i 日目 (1 \leqq i \leqq D) の最高気温は T_i 度であると予報されている．

IOI 君は N 種類の服を持っており，それらには 1 から N までの番号がついている．服 j (1 \leqq j \leqq N) は最高気温が A_j 度以上 B_j 度以下の日に着るのに適している．また，それぞれの服には「派手さ」とよばれる整数が定まっており，服 j の派手さは C_j である．

D 日間のそれぞれに対し，IOI 君は，最高気温が天気予報に従ったときに着るのに適した服のうち 1 つを着る服として選ぶ．同じ服を何度選んでもよいし，D 日間で一度も選ばれない服があってもよい．

似ている服を連続して着ることをなるべく避けようと思った IOI 君は，連続する日に着る服の派手さの差の絶対値の合計をできるだけ大きくしようと考えた．すなわち，i 日目に服 x_i を選んだとして，値 |C_{x_1} - C_{x_2}| + |C_{x_2} - C_{x_3}| + \cdots + |C_{x_{D-1}} - C_{x_D}| を最大にしたい．この最大値を求めるプログラムを作成せよ．

入力例 1

3 4
31
27
35
20 25 30
23 29 90
21 35 60
28 33 40

出力例 1

80

入出力例 1 において，1 日目の服の候補は服 3 と服 4 であり，2 日目の服の候補は服 2 と服 3 であり，3 日目の服の候補は服 3 のみである．1 日目に服 4 を，2 日目に服 2 を，3 日目に服 3 を選ぶ．すなわち，x_1 = 4，x_2 = 2，x_3 = 3 とする．このとき，1 日目と 2 日目の服の派手さの差の絶対値は |40 - 90| = 50 であり，2 日目と 3 日目の服の派手さの差の絶対値は |90 - 60| = 30 である．合計は 80 となり，これが最大値である．

入力例 2

5 2
26
28
32
29
34
30 35 0
25 30 100

出力例 2

300

入出力例 2 において，1 日目には服 2 を，2 日目には服 2 を，3 日目には服 1 を，4 日目には服 2 を，5 日目には服 1 を選ばなければならない．このとき，求める値は |100 - 100| + |100 - 0| + |0 - 100| + |100 - 0| = 300 となる．

問題

オーストラリア大陸の西には，広いインド洋が広がっている．海洋研究者である JOI 氏は，インド洋に生息しているある N 種類の魚の性質について研究している．

それぞれの魚の種類に対して，海の中に直方体状の生息範囲が定まっている．魚は境界も含めて生息範囲の中のどの場所にも移動できるが，生息範囲の外に出ることは決してない．海の中の点は，3 つの実数 (x, y, d) によって表される： (x, y, d) は，上空から見たときにある地点を基準にして東に x ，北に y 進んだ位置であり，海面からの深さが d の点を表す．ただし，海面は平面であるとする．

JOI 氏は，K 種類以上の魚の生息範囲が重なる場所がどのくらいあるかを知りたい．そのような場所全体の体積を求めるプログラムを作成せよ．

入力例 1

3 2
30 50 0 50 70 100
10 20 20 70 90 60
40 60 20 90 90 70

出力例 1

49000

入出力例 1 において，例えば，点 (45, 65, 65) は 1 種類目の魚と 3 種類目の魚の生息範囲であるので，条件を満たす場所である．一方，点 (25, 35, 45) は 2 種類目の魚のみの生息範囲であるので，条件を満たす場所ではない．また，魚の生息範囲は下の図のようになっている．点 O は海面上の基準の地点を表す．

入力例 2

1 1
0 0 0 1000000 1000000 1000000

出力例 2

1000000000000000000

問題

オーストラリアに旅行に来た JOI 君は様々な場所で観光を楽しみ，ついに帰国する日がやってきた．今，JOI 君は帰りの飛行機が出発する国際空港のある町にいる．この町は東西南北に区画整理されており，各区画には道，土産店，住宅，国際空港がある． JOI 君は最も北西の区画から出発して最も南東の区画の国際空港を目指す．

JOI 君は今いる区画から隣り合った区画に移動することができるが，住宅のある区画には入ることはできない．また飛行機の時間に間に合わせるために，今いる区画の東か南の区画にのみ移動する．ただし，時間にはいくらか余裕があるため，K 回まで今いる区画の北か西の区画へ移動することができる．

JOI 君は土産店のある区画に入ると，日本の友人たちのためにお土産を買う．JOI 君は土産店について入念に下調べをしていたので，どの土産店に行ったら何個のお土産を買うことができるかが分かっている．JOI 君が購入できるお土産の個数の最大値を求めるプログラムを作成せよ．

ただし，お土産を買う時間は無視できるとし，同じ土産店に 2 度以上訪れたときは最初に訪れたときだけお土産を買う．

入力例 1

5 4 2
...#
.#.#
.#73
8##.
....

出力例 1

11

入出力例 1 において，JOI 君は 3 回南へ進み区画 (4, 1) の土産店で買い物をした後，さらに南へ 1 回，東へ 3 回進み，そこから北へ 2 回進むことで区画 (3, 4) の土産店で買い物をする．最後に南へ 2 回進んで国際空港へたどり着くと，合計で 11 個のお土産を買うことができる．

入力例 2

4 4 3
.8#9
9.#.
.#9.
....

出力例 2

27