A - 金庫

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたはぬいぐるみを持っています。ぬいぐるみは大切なので鍵をかけて金庫に保管しています。

金庫はダイヤル式で、-100 から 100 までの整数値の目盛りが書かれています。最初 0 に針が合わせられています。

金庫は針が 0 にある状態から始めて、針を A の位置に合わせた後、B の位置に合わせて、再び 0 の位置に合わせることで開けることができます。針を A の位置に合わせる前に針を B の位置に合わせることはできますが、この場合でも針を A の位置に合わせた後に再び B の位置に合わせる必要があります。

針が指す値は 1 ずつしか変化させることができません。ただし、針が -100 を指している状態で針が指す値をさらに減らすこと、針が 100 を指している状態で針が指す値をさらに増やすことはできません。

また、針が指す値を 1 つ変化させる度に音が 1 回鳴ります。例えば針が 0 を指している状態から 1 ずつ針が指す値を増やしていって針が 5 を指すようにした場合には 5 回音が鳴ります。

あなたは金庫が鳴らす音が苦手で、余り音を鳴らしたくないので、音を鳴らす回数として考えられる最小値が知りたいです。

入力

入力は以下の形式で標準入力から与えられる。

A
B
  • 1 行目には、最初に針を合わせるべき整数 A (-100 ≦ A ≦ 100) が与えられる。
  • 2 行目には、次に針を合わせるべき整数 B (-100 ≦ B ≦ 100) が与えられる。
  • A ≠ 0, B ≠ 0, A ≠ B である。

出力

音を鳴らす回数として考えられる最小値を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

5
-2

出力例1

14

針が指す整数を 0 → 1 → 2 → 3 → 4 → 5 → 4 → 3 → 2 → 1 → 0 → -1 → -2 → -1 → 0 と移動させることで音を鳴らす回数を 14 回に抑えることができます。

入力例2

4
3

出力例2

8

先に B で指定された値に針が一致することもあります。

入力例3

-40
-91

出力例3

182
B - 袋とボール

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

2 つの袋 A, B があります。袋 A と袋 B にはボールが 2 つずつ入っています。各ボールには整数が 1 つずつ書かれています。

あなたは袋 A と袋 B からボールを 1 つずつ取り出し、取り出した 2 つのボールに書かれていた整数を確認したかったのですが、困ったことにそのうち 1 つのボールについて、書かれていた整数が読めなくなっていました。さらに、取り出した 2 つのボールが元々どちらの袋に入っていたのかも分からなくなってしまいました。

あなたはもう一方のボールに書かれている整数から、書かれていた整数が読めなくなったボールに書かれていた整数が何だったのかを推測することにしました。

入力

入力は以下の形式で標準入力から与えられる。

A_1 A_2
B_1 B_2
C
  • 1 行目には、2 個の整数 A_1, A_2 (1 ≦ A_1 ≦ A_2 ≦ 100) が空白区切りで与えられる。これは袋 A に入っているボールに書かれた整数が A_1 と A_2 であることを表す。
  • 2 行目には、2 個の整数 B_1, B_2 (1 ≦ B_1 ≦ B_2 ≦ 100) が空白区切りで与えられる。これは袋 B に入っているボールに書かれた整数が B_1 と B_2 であることを表す。
  • 3 行目には、整数 C (1 ≦ C ≦ 100) が与えられる。これは取り出したボールのうち 1 つには C と書かれていたことを表す。
  • C=A_1, C=A_2, C=B_1, C=B_2 のいずれかが成立することが保証される。

出力

読めなくなっていた整数として考えられるものが S_1, ... , S_M (1≦S_1＜...＜S_M≦100) であったとする。このとき出力は M+1 行からなる。

1 行目には、読めなくなっていた整数として考えられるものの個数 M を出力せよ。

2 行目からの M 行のうち i (1≦i≦M) 行目には、整数 S_i を出力せよ。

出力の末尾にも改行を入れること。

入力例1

12 18
19 20
20

出力例1

2
12
18

(袋 A から取り出したボールに書かれていた整数, 袋 B から取り出したボールに書かれていた整数) の組として考えられるものは、(12, 19), (12, 20), (18, 19), (18, 20) の 4 通りあります。このうち片方が 20 となっているもののうちの他方として考えられるものは 12 と 18 です。

入力例2

10 10
20 20
10

出力例2

1
20

(袋 A から取り出したボールに書かれていた整数, 袋 B から取り出したボールに書かれていた整数) の組としては (10, 20) しか考えられません。

入力例3

2 3
1 2
2

出力例3

3
1
2
3
C - 集合写真

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ある研究室には N+1 人の学生がおり、この度写真撮影のために一列に並ぶことになりました。

撮影会場には現時点で N 人の学生がおり、身長が低い順に左から右へと並んでいます。1 人の学生は寝坊したため、急いで撮影会場に向かっているところです。

カメラマンであるあなたは撮影を素早く行うために、会場に向かっている学生に、列の何番目に並べば良いのかを身長のデータを基に算出し伝えることにしました。

入力

入力は以下の形式で標準入力から与えられる。

N
H_1 H_2 ... H_N
X
  • 1 行目には、整数 N (1 ≦ N ≦ 50) が与えられる。これは研究室に学生が N+1 人いることを表す。
  • 2 行目には、N 個の整数 H_1, H_2, ... , H_N (1 ≦ H_1 ＜ H_2 ＜ ... ＜ H_N ≦ 100) が空白区切りで与えられる。これは現時点で列の左から i 番目に並んでいる学生の身長が H_i であることを表す。
  • 3 行目には、整数 X (1 ≦ X ≦ 100) が与えられる。これは寝坊した学生の身長が X であることを表す。
  • H_1, H_2, ... , H_N , X は相異なる。

出力

寝坊した学生が列に加わる際に左から何番目に並ぶかを表す整数を 1 行に出力せよ。

出力の末尾にも改行を入れること。

入力例1

3
11 18 22
17

出力例1

2

寝坊した学生の身長は 17 です。寝坊した学生が加わった後に列は 11, 17, 18, 22 となるので、寝坊した学生は左から 2 番目に入る必要があります。

入力例2

5
30 40 50 60 70
10

出力例2

1

寝坊した学生は先頭に入ることになります。

入力例3

6
11 24 44 56 78 99
100

出力例3

7
D - 暴露

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

1 から N までの番号が付けられた N 人の生徒からなるある学園で期末試験が行われた。試験は 100 点満点で、どの生徒も非負の整数の得点を獲得した。

この学園ではどの生徒も自分の得点と全受験者の合計点を通知されるが、それ以外の情報は通知されない。

しかしながらどの生徒も他の生徒の得点が気になる。そのため生徒は他の生徒から得点を聞き出し、それらの値を基に他の生徒の得点を予想することにしている。

学園の教師であり、生徒が他の生徒の得点をどれくらい正確に把握しているのかが気になったあなたは、生徒の行動によってどのくらい得点が特定できているのかを調査することにした。

具体的には、以下に示す M 個の情報クエリあるいは質問クエリを番号の昇順に処理した際の質問クエリの答えを計算することにした。

  • クエリには 1 から M までの番号が付けられている。どのクエリも 3 つの整数 a_i (0 ≦ a_i ≦ 1), b_i (1 ≦ b_i ≦ N), c_i (1 ≦ c_i ≦ N, b_i≠c_i) によって定められる。
  • a_i = 0 のとき、クエリ i は情報クエリである。これは、生徒 b_i が生徒 c_i の得点を知ったことを表す。
  • a_i = 1 のとき、クエリ i は質問クエリである。これは、生徒 b_i がクエリ i までの情報クエリと元々知っている情報のみで、生徒 c_i の得点が何点以上何点以下であると判定できるのかを答えなければならないことを表す。

入力

入力は以下の形式で標準入力から与えられる。

N
s_1
s_2
:
s_N
M
a_1 b_1 c_1
a_2 b_2 c_2
:
a_M b_M c_M
  • 1 行目には、学園の生徒数 N (2 ≦ N ≦ 50) が与えられる。
  • 2 行目から N 行には、生徒の得点が与えられる。N 行のうち i (1 ≦ i ≦ N) 行目には、生徒 i が獲得した得点 s_i (0 ≦ s_i ≦ 100) が与えられる。
  • N+2 行目には、クエリ数 M (1 ≦ M ≦ 5,000) が与えられる。
  • N+3 行目から M 行には、クエリの情報が与えられる。M 行のうち i (1 ≦ i ≦ M) 行目には、クエリ i を定める 3 つの整数 a_i (0 ≦ a_i ≦ 1), b_i (1 ≦ b_i ≦ N), c_i (1 ≦ c_i ≦ N, b_i≠c_i) が空白区切りで与えられる。
  • 1 ≦ i ＜ j ≦ M となる整数 i, j に対して、a_i = a_j = 0 ならば、b_i ≠ b_j または c_i ≠ c_j が成り立ちます。
  • 入力では 1 ≦ i ≦ M を満たすある整数 i において a_i = 1 であること (すなわち少なくとも 1 つは質問クエリがあること) が保証されています。

出力

M 個のクエリ中の質問クエリ数を Q 個としたとき、出力は Q 行からなる。Q 行のうち i (1 ≦ i ≦ Q) 行目には、i 番目の質問クエリに対する答えを出力せよ。i 番目の質問クエリに対する答えが、x 点以上 y 点以下であるという答えならば、x と y をこの順に空白区切りで出力せよ。出力の末尾にも改行を入れること。

入力例1

4
80
90
70
100
6
0 2 3
0 4 2
1 2 4
0 2 4
1 2 1
1 4 1

出力例1

80 100
80 80
50 100

生徒は 4 人であり、クエリは 6 個ある。

  • クエリ 1 は情報クエリである。生徒 2 は生徒 3 の得点が 70 点であることを知る。
  • クエリ 2 は情報クエリである。生徒 4 は生徒 2 の得点が 90 点であることを知る。
  • クエリ 3 は質問クエリである。この時点で生徒 2 は合計点が 80+90+70+100=340 点であること、生徒 2 の得点が 90 点であること、生徒 3 の得点が 70 点であることを知っているので、生徒 4 の得点は 80 点以上 100 点以下であることがわかる。よって出力の 1 行目は 80 100 となる。
  • クエリ 4 は情報クエリである。生徒 2 は生徒 4 の得点が 100 点であることを知る。
  • クエリ 5 は質問クエリである。この時点で生徒 2 は合計点および生徒 1 以外すべての生徒の得点を知っているので、生徒 1 の得点はちょうど 80 点であることがわかる。よって出力の 2 行目は 80 80 となる。
  • クエリ 6 は質問クエリである。この時点で生徒 4 は合計点が 340 点であること、生徒 2 の得点が 90 点であること、生徒 4 の得点が 100 点であることを知っているので、生徒 1 の得点は 50 点以上 100 点以下であることがわかる。よって出力の 3 行目は 50 100 となる。

入力例2

3
25
12
31
3
1 1 2
0 1 2
1 1 2

出力例2

0 43
12 12

既に得点を知っている相手に対して質問クエリが飛んで来る場合もあります。

入力例3

7
32
19
22
25
23
17
18
11
0 1 2
0 4 5
0 1 4
0 2 3
0 2 7
1 1 5
1 2 7
1 2 1
0 4 3
1 4 2
1 6 7

出力例3

0 80
18 18
0 97
0 86
0 100
E - ノイズ除去

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたはプログラマーとしてとある会社に勤めています。

この会社であなたは、ユーザーから集めた文字列のある連続した部分に指定した文字列が含まれるかを判定する業務をしています。

例えば、文字列 rhd は文字列 thisisrhdcontest に含まれていますが、文字列 thanks や文字列 ratheads には含まれていません。

しかしながら、ユーザーからの問い合わせにより、不要な文字がノイズとしてユーザーから寄せられた文字列に入ってしまいユーザーの希望通りの判定が行われていないことが判明しました。

そこであなたは、以下の Q 個のクエリ 1 から Q を処理するプログラムを作成することになりました。

クエリ i : 「文字列 S_i と文字列 T_i が与えられる。いくつかの文字 x_1, x_2, ... , x_k を選び (1 文字も選ばなくても良い)、文字列 S_i から選んだ文字をすべて取り除くという操作を行って得られる文字列 S'_i として考えられるものの中に文字列 T_i が含まれうるか判定せよ」

例えば、S_1 = ratheads, T_1 = rhd のとき、S_1 から文字 a, e, t を取り除いたときに得られる文字列 S'_1 = rhds には文字列 T_1 = rhd が含まれるため、文字列 T_1 は含まれうるといえます。

入力

入力は以下の形式で標準入力から与えられる。

Q
S_1 T_1
S_2 T_2
:
S_Q T_Q
  • 1 行目には、クエリの個数 Q (1 ≦ Q ≦ 5,000) が与えられる。
  • 2 行目から Q 行には、クエリに関する情報が与えられる。このうち i (1 ≦ i ≦ Q) 行目には半角小文字英字のみで構成される 2 つの文字列 S_i, T_i (1 ≦ ｜S_i｜ ≦ 50, 1 ≦ ｜T_i｜ ≦ 50) が空白区切りで与えられる。

出力

Q 行にわたって出力せよ。Q 行のうち i (1 ≦ i ≦ Q) 行目には、クエリ i に対する答えを出力せよ。もしもクエリ i において文字列 T_i が含まれうるなら YES を、そうでないなら NO を出力せよ。出力の末尾にも改行を入れること。

入力例1

4
ratheads rhd
thisisrhdcontest rhd
yes no
abba aba

出力例1

YES
YES
NO
NO

クエリは 4 つあります。

  • クエリ 1 は、問題文中の例に示されています。S_1 から文字 a, e, t を取り除いたときに得られる文字列 S'_1 = rhds には文字列 T_1 が含まれるので、YES と出力します。
  • クエリ 2 では、文字列 S_2 から文字を取り除かなくても文字列 S_2 に文字列 T_2 が含まれるので YES を出力します。
  • クエリ 3 では、文字列 S_3 からどのように文字を取り除いても文字列 S'_3 に文字列 T_3 が含まれないので NO を出力します。
  • クエリ 4 では、文字列 S_4 からどのように文字を取り除いても文字列 S'_4 に文字列 T_4 が含まれないので NO を出力します。

なお、文字を指定してその文字を取り除くとき、指定した文字を一部取り除かずに残すことができないことに注意してください。

入力例2

5
abcdef bdf
aabbccdd b
abcabcabc aaba
abcdcba dba
ababababa aba

出力例2

YES
YES
NO
YES
YES
F - お祭りとお菓子

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

A さんと B さんはお祭りに参加しています。

お祭りで N 個の実と N-1 本の枝からなるお菓子をもらいました。実には 1 から N までの番号が付けられており、枝には 1 から N-1 までの番号が付けられています。枝 i (1 ≦ i ≦ N-1) は実 s_i と実 t_i を結んでいます。また、実 1 と他のどの実についても、枝を介して連結です。すなわち、2 ≦ X ≦ N を満たすすべての整数 X について、ある数列 a_{X,1}, ... , a_{X,k} (k ≧ 1 かつ 1 ≦ i ≦ k を満たすどの整数 i についても 1 ≦ a_{X,i} ≦ N-1) が存在し、その数列は以下の条件を満たします。

  • 枝 a_{X,1} が結ぶ実に実 1 がある。
  • 1 ≦ i ≦ k-1 を満たす任意の整数 i に関して、枝 a_{X,i} が結ぶ実と枝 a_{X,i+1} が結ぶ実に共通して登場する実がある。
  • 枝 a_{X,k} が結ぶ実に実 X がある。

A さんと B さんは、A さんから始めて交互に実や枝を食べていきます。A さんあるいは B さんは自分の手番において、枝が 1 本以下しか接続されていない実を選んで、その実およびその実と直接接続している枝すべてを同時に食べます。2 本以上の枝と接続されている実はその時点ではまだ食べにくく、無理に食べようとすると口がベトベトになってしまいます。

また、実 1 は特別美味しいため、A さんも B さんも自分の手番で実 1 が食べられるように行動します。

双方が最善を尽くしたときに、一体どちらが実 1 を食べることになるでしょうか。

入力

入力は以下の形式で標準入力から与えられる。

N
s_1 t_1
s_2 t_2
:
s_{N-1} t_{N-1}
  • 1 行目には、実の個数 N (2 ≦ N ≦ 100,000) が与えられる。
  • 2 行目から N-1 行には、枝に関する情報が与えられる。このうち i (1 ≦ i ≦ N-1) 行目には 2 つの整数 s_i, t_i (1 ≦ s_i ＜ t_i ≦ N) が空白区切りで与えられる。これは枝 i が実 s_i と実 t_i を結んでいることを表す。

出力

A さんが実 1 を食べる場合は文字 A を、B さんが実 1 を食べる場合は文字 B を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

6
1 2
1 3
2 4
3 5
3 6

出力例1

A

最初に A さんが実 4 を食べたとします。このとき、B さんが食べられる実は実 2, 5, 6 のいずれかです。

  • B さんが実 2 を食べたならば、直後に A さんが実 1 を食べることができます。
  • B さんが実 5 を食べたならば、直後に A さんが実 6 を食べる選択をとったときに、次の手番で B さんは実 2 か実 3 を食べることになり、その直後 A さんが実 1 を食べることができます。
  • B さんが実 6 を食べたならば、直後に A さんが実 5 を食べる選択をとったときに、次の手番で B さんは実 2 か実 3 を食べることになり、その直後 A さんが実 1 を食べることができます。

以上より両者が最善を尽くしたときに実 1 を食べることができるのは A さんです。

入力例2

5
1 2
2 3
2 4
2 5

出力例2

A

最初に A さんが実 1 を食べることができます。

入力例3

9
1 2
1 3
1 4
3 5
4 6
4 7
7 8
7 9

出力例3

B
G - カメレオン

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

ここはとあるジャングル、あなたの友達のカメレオンが生活しているところです。

ジャングルには N 個の広場があり、広場には 1 から N までの番号が付けられています。また、ジャングルには M 本の道があり、道には 1 から M までの番号が付けられています。どの道も異なる 2 つの広場を結んでいて、双方向に移動可能です。

あなたの友達のカメレオンは、CODE THANKS FESTIVAL 2015 に参加するため、広場 1 から広場 N に向かおうとしています。カメレオンは広場間を移動する際に道を使いますが、ジャングルの道は未知なる危険に満ちあふれているため、道 i (1 ≦ i ≦ M) を使用する際にはカメレオンの体色は色 c_i でなければなりません。また、道 i を使用して移動する際、時間が t_i だけかかります。

カメレオンは広場 1 から移動を開始する際、体色は色 1 です。カメレオンはどの広場でも体色を変化させることができますが、どの広場でも色 x から色 y に体色を変化させるには時間が ｜x-y｜ だけかかってしまいます。またカメレオンは広場 N に到着したならば移動を終了しますが、この際の体色はどの色でも構いません。

あなたは、カメレオンが広場 N に到着するまでにかかるの時間として考えられる最小値を求めることになりました。

入力

入力は以下の形式で標準入力から与えられる。

N M
a_1 b_1 c_1 t_1
a_2 b_2 c_2 t_2
:
a_M b_M c_M t_M
  • 1 行目には、広場の個数 N (2 ≦ N ≦ 40,000) および道の本数 M (1 ≦ M ≦ 80,000) が空白区切りで与えられる。
  • 2 行目から M 行には、道に関する情報が与えられる。このうち i (1 ≦ i ≦ M) 行目では 4 つの整数値 a_i, b_i (1 ≦ a_i ＜ b_i ≦ N), c_i (1 ≦ c_i ≦ 1,000,000,000), t_i (1 ≦ t_i ≦ 1,000,000,000) が空白区切りで与えられる。これは、道 i が広場 a_i と b_i を結んでおり、道 i を渡る際には体色が色 c_i でなければならず、移動に時間が t_i かかることを表す。
  • i ≠ j ならば、a_i ≠ a_j あるいは b_i ≠ b_j が成立する。
  • 広場 1 から他のどの広場にも 1 本以上の道を経由して行き来できることは保証されている。

出力

カメレオンが広場 N に到着するまでにかかる時間として考えられる最小値を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

6 7
1 2 1 6
1 3 7 4
2 3 3 4
2 5 6 6
3 4 4 6
3 5 1 3
5 6 2 4

出力例1

22

この入力例の場合、以下のように移動するのが最適です。

  • 最初、広場 1 に体色が色 1 のカメレオンがいます。
  • 道 1 を用いて広場 1 から広場 2 に移動します。カメレオンの体色が色 1 なので移動可能であり、合計でかかった時間は 6 となります。
  • 広場 2 で体色を色 1 から色 3 に変化させます。合計でかかった時間は 6+2 = 8 となります。
  • 道 3 を用いて広場 2 から広場 3 に移動します。カメレオンの体色が色 3 なので移動可能であり、合計でかかった時間は 8+4 = 12 となります。
  • 広場 3 で体色を色 3 から色 1 に変化させます。合計でかかった時間は 12+2 = 14 となります。
  • 道 6 を用いて広場 3 から広場 5 に移動します。カメレオンの体色が色 1 なので移動可能であり、合計でかかった時間は 14+3 = 17 となります。
  • 広場 6 で体色を色 1 から色 2 に変化させます。合計でかかった時間は 17+1 = 18 となります。
  • 道 7 を用いて広場 5 から広場 6 に移動します。カメレオンの体色が色 2 なので移動可能であり、合計でかかった時間は 18+4 = 22 となります。

入力例2

3 3
1 2 1 10
1 3 3 3
2 3 5 2

出力例2

5
H - 穴あきケーキ

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

クリスマスの時期が近づいてきました。あなたは友達のためにクリスマスケーキとして穴あきケーキを作ることになりました。

穴あきケーキを作るために用いるケーキ生地は R 行 C 列の長方形状であり、i (1 ≦ i ≦ R) 行 j (1 ≦ j ≦ C) 列の領域を領域 (i, j) と呼ぶことにします。領域 (i, j) を食べたとき、C_{i,j} キロカロリー得られます。また、領域 (1, 1) が左上隅、領域 (R, C) が右下隅です。

あなたはこのケーキ生地を以下の手順によって穴あきケーキに加工します。

  • まず、4 つの整数 a, b, c, d (1 ≦ a ＜ b ≦ R, 1 ≦ c ＜ d ≦ C, b - a ≧ 2, d - c ≧ 2) を定めます。ケーキ生地のうち、領域 (a, c) を左上、(b, d) を右下とした長方形の部分を切り出します。
  • 先の手順で切り出した部分について、端に存在しない領域 1 つ (領域 (e, f) (a+1 ≦ e ≦ b-1, c+1 ≦ f ≦ d-1) とする) を選んで削除し、残りを穴あきケーキとします。

また、穴あきケーキの摂取カロリーは、穴あきケーキを構成する領域に定められたカロリーの合計値となります。

健康志向の友達は穴あきケーキを食べることによって得られる摂取カロリーがちょうど K キロカロリーとなるようなケーキを希望しています。あなたは条件を満たす穴あきケーキとして考えられるものの総数、すなわち、上記の条件を満たす 6 つの整数 a, b, c, d, e, f の選び方が全部で何通りあるかを計算することにしました。

入力

入力は以下の形式で標準入力から与えられる。

R C K
s_1
s_2
:
s_R
  • 1 行目には、ケーキ生地の行数 R (3 ≦ R ≦ 350)、列数 C (3 ≦ C ≦ 350) および友達が希望している摂取カロリー量 K (0 ≦ K ≦ 999,999) が空白区切りで与えられる。
  • 2 行目から R 行には、ケーキ生地のカロリーに関する情報が与えられる。このうち i (1 ≦ i ≦ R) 行目では 長さ C の文字列 s_i が与えられる。s_i を構成する文字はいずれも 1 から 9 までの数字である。s_i の左から j (1 ≦ j ≦ C) 文字目の数字は、領域 (i, j) を穴あきケーキに含めることによって増加するカロリー量 C_{i,j} に等しい。

出力

穴あきケーキとして考えられる総数を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

4 5 14
54311
11211
17312
11119

出力例1

2

ケーキ生地は下表のようになっています。

5 4 3 1 1
1 1 2 1 1
1 7 3 1 2
1 1 1 1 9

例えば、a = 2, b = 4, c = 1, d = 4 として切り出した場合、以下の領域が切り出されます。

1 1 2 1
1 7 3 1
1 1 1 1

さらに、e = 3, f = 2 として穴を開けると、穴あきケーキは以下の形状となります (* は穴を開けた場所を表す)。

1 1 2 1
1 * 3 1
1 1 1 1

このとき、摂取カロリーは、1+1+2+1+1+3+1+1+1+1+1 = 14 となり、条件を満たします。

他にも a = 1, b = 3, c = 3, d = 5, e = 2, f = 4 のときに条件を満たします。

入力例2

6 7 8
1111116
1111111
1111115
1113111
1211111
1111141

出力例2

7

穴あきケーキを構成する領域のカロリーの配置が同じでも、切り出す場所、穴を開ける場所が異なれば異なるケーキとして数えます。

入力例3

3 3 9
211
121
112

出力例3

0

条件を満たす穴あきケーキが存在しない場合もあります。

入力例4

8 8 15
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111

出力例4

100