Toyota Programming Contest 2023#4（AtCoder Beginner Contest 311）

A - First ABC

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

A, B, C からなる文字列 S が与えられます。S は A, B, C を全て含むことが保証されます。

S を左から 1 文字ずつ見ていったときに、はじめて次の条件を満たした状態になるのは、左から何文字目まで見たときですか？

A, B, C が全て 1 回以上出現している。

制約

3 \leq N \leq 100
S は A, B, C からなる長さ N の文字列
S は A, B, C を全て含む

入力

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

N
S

出力

答えを出力せよ。

入力例 1

5
ACABB

出力例 1

左から 4 文字目までに A は 2 回, B は 1 回, C は 1 回出現していて、条件を満たします。
3 文字目以前では条件を満たさないので答えは 4 です。

入力例 2

4
CABC

出力例 2

左から 3 文字目までに A, B, C は 1 回ずつ出現していて、条件を満たします。

入力例 3

30
AABABBBABABBABABCABACAABCBACCA

出力例 3

Score : 100 points

Problem Statement

You are given a string S consisting of A, B, and C. S is guaranteed to contain all of A, B, and C.

If the characters of S are checked one by one from the left, how many characters will have been checked when the following condition is satisfied for the first time?

All of A, B, and C have appeared at least once.

Constraints

3 \leq N \leq 100
S is a string of length N consisting of A, B, and C.
S contains all of A, B, and C.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

5
ACABB

Sample Output 1

In the first four characters from the left, A, B, and C appear twice, once, and once, respectively, satisfying the condition.
The condition is not satisfied by checking three or fewer characters, so the answer is 4.

Sample Input 2

4
CABC

Sample Output 2

In the first three characters from the left, each of A, B, and C appears once, satisfying the condition.

Sample Input 3

30
AABABBBABABBABABCABACAABCBACCA

Sample Output 3

B - Vacation Together

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 から N までの番号がついた N 人の人がいます。
N 人の人の今後 D 日間の予定が与えられます。人 i の予定は長さ D の文字列 S_i で表されて、S_i の j 文字目が o ならば j 日目は暇であることを、x ならばそうでないことを意味します。

D 日間のうち全員が暇であるような 連続する 何日かを選ぶことを考えます。
選べる日数は最大で何日ですか？ただし、選べる日が存在しない場合は 0 日と答えてください。

制約

1 \leq N \leq 100
1 \leq D \leq 100
N, D は整数
S_i は o と x からなる長さ D の文字列

入力

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

N D
S_1
S_2
\vdots
S_N

出力

選べる日数の最大値を出力せよ。選べる日が存在しない場合は 0 を出力せよ。

入力例 1

3 5
xooox
oooxx
oooxo

出力例 1

2 日目と 3 日目は全員が暇な日なので選ぶことができます。
この 2 日間を選ぶと、連続する日にちを選ぶ方法の中で日数を最大にすることができます。

入力例 2

3 3
oxo
oxo
oxo

出力例 2

選ぶ日にちは連続している必要があるのに注意してください。(1 日目と 3 日目は全員が暇な日なので選ぶことができますが、この 2 つを同時に選ぶことはできません)

入力例 3

3 3
oox
oxo
xoo

出力例 3

選べる日が存在しない場合は 0 を出力してください。

入力例 4

1 7
ooooooo

出力例 4

入力例 5

5 15
oxooooooooooooo
oxooxooooooooox
oxoooooooooooox
oxxxooooooxooox
oxooooooooxooox

出力例 5

Score : 200 points

Problem Statement

There are N people numbered 1 to N.
You are given their schedule for the following D days. The schedule for person i is represented by a string S_i of length D. If the j-th character of S_i is o, person i is free on the j-th day; if it is x, they are occupied that day.

From these D days, consider choosing some consecutive days when all the people are free.
How many days can be chosen at most? If no day can be chosen, report 0.

Constraints

1 \leq N \leq 100
1 \leq D \leq 100
N and D are integers.
S_i is a string of length D consisting of o and x.

Input

The input is given from Standard Input in the following format:

N D
S_1
S_2
\vdots
S_N

Output

Print the maximum number of days that can be chosen, or 0 if no day can be chosen.

Sample Input 1

3 5
xooox
oooxx
oooxo

Sample Output 1

All the people are free on the second and third days, so we can choose them.
Choosing these two days will maximize the number of days among all possible choices.

Sample Input 2

3 3
oxo
oxo
oxo

Sample Output 2

Note that the chosen days must be consecutive. (All the people are free on the first and third days, so we can choose either of them, but not both.)

Sample Input 3

3 3
oox
oxo
xoo

Sample Output 3

Print 0 if no day can be chosen.

Sample Input 4

1 7
ooooooo

Sample Output 4

Sample Input 5

5 15
oxooooooooooooo
oxooxooooooooox
oxoooooooooooox
oxxxooooooxooox
oxooooooooxooox

Sample Output 5

C - Find it!

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

N 頂点 N 辺の有向グラフがあります。
i 番目の辺は頂点 i から頂点 A_i に伸びます。 ( i \neq A_i であることは制約より保証されます )
同一頂点を複数回含まない有向閉路をひとつ求めてください。
なお、この問題の制約下で答えが存在することが示せます。

注釈

この問題では、有向閉路とは以下の条件を全て満たす頂点の列 B=(B_1,B_2,\dots,B_M) であるとします。

M \ge 2
B_i から B_{i+1} に辺が伸びている。 ( 1 \le i \le M-1 )
B_M から B_1 に辺が伸びている。
i \neq j ならば B_i \neq B_j

制約

入力は全て整数
2 \le N \le 2 \times 10^5
1 \le A_i \le N
A_i \neq i

入力

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

N
A_1 A_2 \dots A_N

出力

以下の形式で出力せよ。

M
B_1 B_2 \dots B_M

M は出力する有向閉路の頂点数であり、 B_i は有向閉路の i 番目の頂点である。
出力は以下の条件を満たす必要がある。

2 \le M
B_{i+1} = A_{B_i} ( 1 \le i \le M-1 )
B_{1} = A_{B_M}
B_i \neq B_j ( i \neq j )

答えとして考えられるものが複数ある場合、どれを出力しても正解となる。

入力例 1

7
6 7 2 1 3 4 5

出力例 1

4
7 5 3 2

7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 は確かに有向閉路になっています。

この入力に対応するグラフは以下の通りです。

他の正解となる出力の例は以下の通りです。

4
2 7 5 3

3
4 1 6

グラフが連結であるとは限らないことに注意してください。

入力例 2

2
2 1

出力例 2

2
1 2

1 \rightarrow 2 と 2 \rightarrow 1 の辺が双方存在するケースです。
この場合、 1 \rightarrow 2 \rightarrow 1 は確かに有向閉路になっています。

この入力に対応するグラフは以下の通りです。
図中 1 \leftrightarrow 2 で 1 \rightarrow 2 と 2 \rightarrow 1 の辺が双方あることを表現しています。

入力例 3

8
3 7 4 7 3 3 8 2

出力例 3

3
2 7 8

この入力に対応するグラフは以下の通りです。

Score : 350 points

Problem Statement

There is a directed graph with N vertices and N edges.
The i-th edge goes from vertex i to vertex A_i. (The constraints guarantee that i \neq A_i.)
Find a directed cycle without the same vertex appearing multiple times.
It can be shown that a solution exists under the constraints of this problem.

Notes

The sequence of vertices B = (B_1, B_2, \dots, B_M) is called a directed cycle when all of the following conditions are satisfied:

M \geq 2
The edge from vertex B_i to vertex B_{i+1} exists. (1 \leq i \leq M-1)
The edge from vertex B_M to vertex B_1 exists.
If i \neq j, then B_i \neq B_j.

Constraints

All input values are integers.
2 \le N \le 2 \times 10^5
1 \le A_i \le N
A_i \neq i

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print a solution in the following format:

M
B_1 B_2 \dots B_M

M is the number of vertices, and B_i is the i-th vertex in the directed cycle.
The following conditions must be satisfied:

2 \le M
B_{i+1} = A_{B_i} ( 1 \le i \le M-1 )
B_{1} = A_{B_M}
B_i \neq B_j ( i \neq j )

If multiple solutions exist, any of them will be accepted.

Sample Input 1

7
6 7 2 1 3 4 5

Sample Output 1

4
7 5 3 2

7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 is indeed a directed cycle.

Here is the graph corresponding to this input:

Here are other acceptable outputs:

4
2 7 5 3

3
4 1 6

Note that the graph may not be connected.

Sample Input 2

2
2 1

Sample Output 2

2
1 2

This case contains both of the edges 1 \rightarrow 2 and 2 \rightarrow 1.
In this case, 1 \rightarrow 2 \rightarrow 1 is indeed a directed cycle.

Here is the graph corresponding to this input, where 1 \leftrightarrow 2 represents the existence of both 1 \rightarrow 2 and 2 \rightarrow 1:

Sample Input 3

8
3 7 4 7 3 3 8 2

Sample Output 3

3
2 7 8

Here is the graph corresponding to this input:

D - Grid Ice Floor

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N \times M のグリッドがあり、この上にプレイヤーがいます。
このグリッドの上から i 行目、左から j 列目をマス (i,j) と書きます。
このグリッドの各マスは氷か岩であり、その情報は N 個の長さ M の文字列 S_1,S_2,\dots,S_N として与えられます。

もし S_i の j 文字目が . なら、マス (i,j) は氷である。
もし S_i の j 文字目が # なら、マス (i,j) は岩である。

なお、このグリッドの外周 ( 1 行目、 N 行目、 1 列目、 M 列目の全てのマス ) は岩です。

最初、プレイヤーはマス (2,2) の上で停止しています。このマスは氷です。
プレイヤーは以下の行動を 0 度以上何度でも行うことができます。

まず、プレイヤーは上下左右の移動方向を指定する。
その後、プレイヤーは岩のマスにぶつかるまでその方向に移動する。厳密には以下の通りである。
- もし移動方向に隣接するマスが氷なら、そのマスに移動し、同じ方向に移動を継続する。
- もし移動方向に隣接するマスが岩なら、今いるマスに留まり、移動を終了する。

プレイヤーが触れる (通過または上で停止する) ことができる氷の数を求めてください。

制約

3 \le N,M \le 200
S_i は # と . からなる長さ M の文字列
i=1 または i=N または j=1 または j=M であるとき、マス (i,j) は岩
マス (2,2) は氷

入力

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

N M
S_1
S_2
\vdots
S_N

出力

答えを整数として出力せよ。

入力例 1

6 6
######
#....#
#.#..#
#..#.#
#....#
######

出力例 1

例えばマス (5,5) には以下のように移動することで上で停止することができます。

(2,2) \rightarrow (5,2) \rightarrow (5,5)

例えばマス (2,4) には以下のように移動することで通過することができます。

(2,2) \rightarrow (2,5) の移動中に (2,4) を通過する。

例えばマス (3,4) は通過することも上で停止することもできません。

入力例 2

21 25
#########################
#..............###...####
#..............#..#...###
#........###...#...#...##
#........#..#..#........#
#...##...#..#..#...#....#
#..#..#..###...#..#.....#
#..#..#..#..#..###......#
#..####..#..#...........#
#..#..#..###............#
#..#..#.................#
#........##.............#
#.......#..#............#
#..........#....#.......#
#........###...##....#..#
#..........#..#.#...##..#
#.......#..#....#..#.#..#
##.......##.....#....#..#
###.............#....#..#
####.................#..#
#########################

出力例 2

Score : 400 points

Problem Statement

There is an N \times M grid and a player standing on it.
Let (i,j) denote the square at the i-th row from the top and j-th column from the left of this grid.
Each square of this grid is ice or rock, which is represented by N strings S_1,S_2,\dots,S_N of length M as follows:

if the j-th character of S_i is ., square (i,j) is ice;
if the j-th character of S_i is #, square (i,j) is rock.

The outer periphery of this grid (all squares in the 1-st row, N-th row, 1-st column, M-th column) is rock.

Initially, the player rests on the square (2,2), which is ice.
The player can make the following move zero or more times.

First, specify the direction of movement: up, down, left, or right.
Then, keep moving in that direction until the player bumps against a rock. Formally, keep doing the following:
- if the next square in the direction of movement is ice, go to that square and keep moving;
- if the next square in the direction of movement is rock, stay in the current square and stop moving.

Find the number of ice squares the player can touch (pass or rest on).

Constraints

3 \le N,M \le 200
S_i is a string of length M consisting of # and ..
Square (i, j) is rock if i=1, i=N, j=1, or j=M.
Square (2,2) is ice.

Input

The input is given from Standard Input in the following format:

N M
S_1
S_2
\vdots
S_N

Output

Print the answer as an integer.

Sample Input 1

6 6
######
#....#
#.#..#
#..#.#
#....#
######

Sample Output 1

For instance, the player can rest on (5,5) by moving as follows:

(2,2) \rightarrow (5,2) \rightarrow (5,5).

The player can pass (2,4) by moving as follows:

(2,2) \rightarrow (2,5), passing (2,4) in the process.

The player cannot pass or rest on (3,4).

Sample Input 2

21 25
#########################
#..............###...####
#..............#..#...###
#........###...#...#...##
#........#..#..#........#
#...##...#..#..#...#....#
#..#..#..###...#..#.....#
#..#..#..#..#..###......#
#..####..#..#...........#
#..#..#..###............#
#..#..#.................#
#........##.............#
#.......#..#............#
#..........#....#.......#
#........###...##....#..#
#..........#..#.#...##..#
#.......#..#....#..#.#..#
##.......##.....#....#..#
###.............#....#..#
####.................#..#
#########################

Sample Output 2

E - Defect-free Squares

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

縦 H 行, 横 W 列のグリッドがあります。グリッドの上から i 行目, 左から j 列目のマスを (i, j) と呼びます。
グリッドの各マスは穴の空いたマスとそうでないマスのどちらかです。穴が空いたマスは (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N) のちょうど N マスです。

正整数の組 (i, j, n) が次の条件を満たすとき、(i, j) を左上隅, (i + n - 1, j + n - 1) を右下隅とする正方形領域を 穴のない正方形 と呼びます。

i + n - 1 \leq H
j + n - 1 \leq W
0 \leq k \leq n - 1, 0 \leq l \leq n - 1 を満たす全ての非負整数の組 (k, l) に対して、(i + k, j + l) は穴が空いていないマスである。

グリッド内に穴のない正方形は何個ありますか？

制約

1 \leq H, W \leq 3000
0 \leq N \leq \min(H \times W, 10^5)
1 \leq a_i \leq H
1 \leq b_i \leq W
(a_i, b_i) は互いに異なる
入力される値は全て整数

入力

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

H W N
a_1 b_1
a_2 b_2
\vdots
a_N b_N

出力

穴のない正方形の個数を出力せよ。

入力例 1

2 3 1
2 3

出力例 1

穴のない正方形は全部で 6 個あります。
それらを列挙すると次の通りです。このうちはじめの 5 個は n = 1 の場合であり、領域の左上隅のマスと右下隅のマスが一致します。

(1, 1) を左上隅かつ右下隅とする正方形領域
(1, 2) を左上隅かつ右下隅とする正方形領域
(1, 3) を左上隅かつ右下隅とする正方形領域
(2, 1) を左上隅かつ右下隅とする正方形領域
(2, 2) を左上隅かつ右下隅とする正方形領域
(1, 1) を左上隅, (2, 2) を右下隅とする正方形領域

入力例 2

出力例 2

穴のない正方形が存在しない場合もあります。

入力例 3

1 1 0

出力例 3

穴のない正方形がグリッド全体と一致する場合もあります。

入力例 4

3000 3000 0

出力例 4

9004500500

Score : 475 points

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left of the grid.
Each square of the grid is holed or not. There are exactly N holed squares: (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N).

When the triple of positive integers (i, j, n) satisfies the following condition, the square region whose top-left corner is (i, j) and whose bottom-right corner is (i + n - 1, j + n - 1) is called a holeless square.

i + n - 1 \leq H.
j + n - 1 \leq W.
For every pair of non-negative integers (k, l) such that 0 \leq k \leq n - 1, 0 \leq l \leq n - 1, square (i + k, j + l) is not holed.

How many holeless squares are in the grid?

Constraints

1 \leq H, W \leq 3000
0 \leq N \leq \min(H \times W, 10^5)
1 \leq a_i \leq H
1 \leq b_i \leq W
All (a_i, b_i) are pairwise different.
All input values are integers.

Input

The input is given from Standard Input in the following format:

H W N
a_1 b_1
a_2 b_2
\vdots
a_N b_N

Output

Print the number of holeless squares.

Sample Input 1

2 3 1
2 3

Sample Output 1

There are six holeless squares, listed below. For the first five, n = 1, and the top-left and bottom-right corners are the same square.

The square region whose top-left and bottom-right corners are (1, 1).
The square region whose top-left and bottom-right corners are (1, 2).
The square region whose top-left and bottom-right corners are (1, 3).
The square region whose top-left and bottom-right corners are (2, 1).
The square region whose top-left and bottom-right corners are (2, 2).
The square region whose top-left corner is (1, 1) and whose bottom-right corner is (2, 2).

Sample Input 2

Sample Output 2

There may be no holeless square.

Sample Input 3

1 1 0

Sample Output 3

The whole grid may be a holeless square.

Sample Input 4

3000 3000 0

Sample Output 4

9004500500

F - Yet Another Grid Task

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

N \times M のグリッドがあります。
このグリッドの上から i 行目、左から j 列目のマスを (i,j) と書きます。
このグリッドの各マスは白か黒であり、その情報は N 個の長さ M の文字列 S_1,S_2,\dots,S_N として与えられます。

もし S_i の j 文字目が . なら、マス (i,j) は白である。
もし S_i の j 文字目が # なら、マス (i,j) は黒である。

以下の条件を満たすグリッドを 美しい グリッドと呼びます。

全ての 1 \le i \le N, 1 \le j \le M を満たす整数組 (i,j) について、マス (i,j) が黒であれば、その下と右下のマスも (存在すれば) 黒である。
厳密には、以下の条件を全て満たす。
- マス (i,j) が黒でありマス (i+1,j) が存在するなら、マス (i+1,j) も黒である。
- マス (i,j) が黒でありマス (i+1,j+1) が存在するなら、マス (i+1,j+1) も黒である。

高橋くんは、白のマスを 0 個以上何個でも黒に塗ることができ、この操作によってグリッドを美しくしようとしています。
高橋くんが作ることのできる美しいグリッドの種類数を 998244353 で割った余りを求めてください。
但し、ある 2 つのグリッドが異なるとは、両者で色が異なるマスが存在することを指します。

制約

1 \le N,M \le 2000
S_i は . と # からなる長さ M の文字列

入力

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

N M
S_1
S_2
\vdots
S_N

出力

答えを整数として出力せよ。

入力例 1

2 2
.#
..

出力例 1

作ることのできる美しいグリッドは以下の 3 種類です。

.#  .#  ##
.#  ##  ##

入力例 2

5 5
....#
...#.
..#..
.#.#.
#...#

出力例 2

入力例 3

25 25
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................

出力例 3

604936632

998244353 で割った余りを求めてください。

Score : 525 points

Problem Statement

There is an N \times M grid and a player standing on it.
Let (i,j) denote the square at the i-th row from the top and j-th column from the left of this grid.
Each square of this grid is black or white, which is represented by N strings S_1,S_2,\dots,S_N of length M as follows:

if the j-th character of S_i is ., square (i,j) is white;
if the j-th character of S_i is #, square (i,j) is black.

The grid is said to be beautiful when the following condition is satisfied.

For every pair of integers (i,j) such that 1 \le i \le N, 1 \le j \le M, if square (i,j) is black, the square under (i,j) and the square to the immediate lower right of (i,j) are also black (if they exist).
Formally, all of the following are satisfied.
- If square (i,j) is black and square (i+1,j) exists, square (i+1,j) is also black.
- If square (i,j) is black and square (i+1,j+1) exists, square (i+1,j+1) is also black.

Takahashi can paint zero or more white squares black, and he will do so to make the grid beautiful.
Find the number of different beautiful grids he can make, modulo 998244353.
Two grids are considered different when there is a square that has different colors in those two grids.

Constraints

1 \le N,M \le 2000
S_i is a string of length M consisting of . and #.

Input

The input is given from Standard Input in the following format:

N M
S_1
S_2
\vdots
S_N

Output

Print the answer as an integer.

Sample Input 1

2 2
.#
..

Sample Output 1

He can make the following three different beautiful grids:

.#  .#  ##
.#  ##  ##

Sample Input 2

5 5
....#
...#.
..#..
.#.#.
#...#

Sample Output 2

Sample Input 3

25 25
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................
.........................

Sample Output 3

604936632

Find the count modulo 998244353.

G - One More Grid Task

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 575 点

問題文

N \times M のグリッドがあり、上から i 行目、左から j 列目のマス (i,j) には非負整数 A_{i,j} が書かれています。
このグリッドのうち長方領域をひとつ選び、それを R とします。
厳密には、長方領域は以下の手順で選ばれます。

1 \le l_x \le r_x \le N, 1 \le l_y \le r_y \le M なる整数 l_x, r_x, l_y, r_y を選ぶ。
このとき、整数 i,j が l_x \le i \le r_x かつ l_y \le j \le r_y を満たす、またその時に限って、マス (i,j) は R に含まれる。

適切に R を選ぶことによって、 f(R) = ( R 内のマスに書かれた整数の総和 ) \times ( R 内のマスに書かれた整数の最小値 ) として達成可能な最大値を求めてください。

制約

入力は全て整数
1 \le N,M \le 300
1 \le A_{i,j} \le 300

入力

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

N M
A_{1,1} A_{1,2} \dots A_{1,M}
A_{2,1} A_{2,2} \dots A_{2,M}
\vdots
A_{N,1} A_{N,2} \dots A_{N,M}

出力

答えを整数として出力せよ。

入力例 1

出力例 1

左上がマス (1,1) 、右下がマス (2,2) の長方領域を選ぶことで、 f(R) = (5+4+4+3) \times \min(5,4,4,3) = 48 が達成でき、これが達成可能な最大値です。

入力例 2

出力例 2

入力例 3

6 6
1 300 300 300 300 300
300 1 300 300 300 300
300 300 1 300 300 300
300 300 300 1 300 300
300 300 300 300 1 300
300 300 300 300 300 1

出力例 3

Score : 575 points

Problem Statement

There is an N \times M grid, where the square at the i-th row from the top and j-th column from the left has a non-negative integer A_{i,j} written on it.
Let us choose a rectangular region R.
Formally, the region is chosen as follows.

Choose integers l_x, r_x, l_y, r_y such that 1 \le l_x \le r_x \le N, 1 \le l_y \le r_y \le M.
Then, square (i,j) is in R if and only if l_x \le i \le r_x and l_y \le j \le r_y.

Find the maximum possible value of f(R) = (the sum of integers written on the squares in R) \times (the smallest integer written on a square in R).

Constraints

All input values are integers.
1 \le N,M \le 300
1 \le A_{i,j} \le 300

Input

The input is given from Standard Input in the following format:

N M
A_{1,1} A_{1,2} \dots A_{1,M}
A_{2,1} A_{2,2} \dots A_{2,M}
\vdots
A_{N,1} A_{N,2} \dots A_{N,M}

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

Choosing the rectangular region whose top-left corner is square (1, 1) and whose bottom-right corner is square (2, 2) achieves f(R) = (5+4+4+3) \times \min(5,4,4,3) = 48, which is the maximum possible value.

Sample Input 2

Sample Output 2

Sample Input 3

6 6
1 300 300 300 300 300
300 1 300 300 300 300
300 300 1 300 300 300
300 300 300 1 300 300
300 300 300 300 1 300
300 300 300 300 300 1

Sample Output 3

Ex - Many Illumination Plans

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 675 点

問題文

頂点に 1 から N までの番号がついた N 頂点の根付き木 T があります。根は頂点 1 で、頂点 i (2 \leq i \leq N) の親は P_i です。
各頂点には 美しさ・重さと呼ばれる 2 つの非負整数値がついています。頂点 i の美しさは B_i で重さは W_i です。
また、各頂点は赤か青で塗られています。頂点 i の色は整数 C_i で表されて、C_i = 0 のとき頂点 i は赤、C_i = 1 のとき青で塗られています。

頂点 v に対して、次の問題の答えを F(v) とおきます。

T から v を根とする部分根付き木を取り出して出来る根付き木を U とします。
あなたは U に対して以下の一連の操作を 0 回以上好きなだけ行うことができます。(操作の前後で、削除されない頂点の美しさ・重さ・色はいずれも変化しません。)

根以外の頂点 c を 1 つ選ぶ。c の親を p とする。

頂点 c が親側の端点である辺全てに対して、次の操作を行う。

辺の c でない端点を u とする。辺を削除して、代わりに p, u 間に p を親側の端点とする新たな辺を結ぶ。

頂点 c 、および p, c 間を結ぶ辺を削除する。

操作後の U としてあり得る根付き木のうち、以下の条件を全て満たす木を 良い根付き木 と呼びます。

U に含まれるすべての辺について、辺で結ばれた頂点同士の色が異なる。

頂点の重さの総和が X 以下である。

良い根付き木に含まれる頂点の美しさの総和として取り得る値の最大値を求めてください。

F(1), F(2), \dots, F(N) を全て列挙してください。

制約

2 \leq N \leq 200
0 \leq X \leq 50000
1 \leq P_i \leq i - 1
0 \leq B_i \leq 10^{15}
0 \leq W_i \leq X
C_i は 0 または 1
入力される値はすべて整数

入力

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

N X
P_2 P_3 \dots P_N
B_1 W_1 C_1
B_2 W_2 C_2
\vdots
B_N W_N C_N

出力

N 行出力せよ。i 行目には F(i) を出力せよ。

入力例 1

出力例 1

v=1 の場合、まず c=2 を選び、次に c=3 を選ぶと U は図のように変化して、操作後の U は良い根付き木になります。この木に含まれる頂点の美しさの総和は 2 + 7 = 9 で、良い根付き木の中で最大です。よって F(1) = 9 です。

v=2 の場合、 c=4 を選ぶと U は図のように変化して、操作後の U は良い根付き木になります。この木に含まれる頂点の美しさの総和は 4 + 6 = 10 で、良い根付き木の中で最大です。よって F(2) = 10 です。

入力例 2

出力例 2

入力例 3

20 100
1 2 1 1 1 6 6 5 1 7 9 4 6 4 15 16 8 2 5
887945036308847 12 0
699398807312293 20 1
501806283312516 17 0
559755618233839 19 1
253673279319163 10 1
745815685342299 11 1
251710263962529 15 0
777195295276573 15 0
408579800634972 17 0
521840965162492 17 1
730678137312837 18 1
370007714721362 14 1
474595536466754 17 0
879365432938644 15 0
291785577961862 20 0
835878893889428 14 1
503562238579284 10 0
567569163005307 18 1
368949585722534 15 0
386435396601075 16 0

出力例 3

5329161389647368
1570154676347343
501806283312516
2665577865131167
1418696191276572
3952333977838189
982388401275366
1344764458281880
778587515356334
521840965162492
730678137312837
370007714721362
474595536466754
879365432938644
1631226710430574
1339441132468712
503562238579284
567569163005307
368949585722534
386435396601075

Score : 675 points

Problem Statement

There is a rooted tree T with N vertices numbered 1 to N. The root is vertex 1, and the parent of vertex i (2 \leq i \leq N) is P_i.
Each vertex has two non-negative integer values called beauty and weight. The beauty and weight of vertex i are B_i and W_i, respectively.
Additionally, each vertex is painted red or blue. The color of vertex i is represented by an integer C_i: vertex i is painted red if C_i = 0, and blue if C_i = 1.

For vertex v, let F(v) be the answer to the following problem.

Let U be the rooted tree that is the subtree of T rooted at v.
You can perform the following sequence of operations on U zero or more times. (The operations do not affect the beauties, weights, or colors of the vertices that are not being deleted.)

Choose a vertex c other than the root. Let p be the parent of c.

For each edge whose endpoint on the parent side is c, do the following:

Let u be the endpoint of the edge other than c. Delete the edge and connect p and u with a new edge, with p on the parent side.

Delete the vertex c, and the edge connecting p and c.

A rooted tree that can be obtained as U after some operations is called a good rooted tree when all of the following conditions are satisfied.

For every edge in U, the edge's endpoints have different colors.

The vertices have a total weight of at most X.

Find the maximum possible total beauty of the vertices in a good rooted tree.

Find all of F(1), F(2), \dots, F(N).

Constraints

2 \leq N \leq 200
0 \leq X \leq 50000
1 \leq P_i \leq i - 1
0 \leq B_i \leq 10^{15}
0 \leq W_i \leq X
C_i is 0 or 1.
All input values are integers.

Input

The input is given from Standard Input in the following format:

N X
P_2 P_3 \dots P_N
B_1 W_1 C_1
B_2 W_2 C_2
\vdots
B_N W_N C_N

Output

Print N lines. The i-th line should contain F(i).

Sample Input 1

Sample Output 1

For v=1, choosing c=2 and then c=3 changes U as shown in the figure, making it a good rooted tree. The total beauty of the vertices in this tree is 2 + 7 = 9, which is the maximum among all good rooted trees, so F(1) = 9.

For v=2, choosing c=4 changes U as shown in the figure, making it a good rooted tree. The total beauty of the vertices in this tree is 4 + 6 = 10, which is the maximum among all good rooted trees, so F(2) = 10.

Sample Input 2

Sample Output 2

Sample Input 3

20 100
1 2 1 1 1 6 6 5 1 7 9 4 6 4 15 16 8 2 5
887945036308847 12 0
699398807312293 20 1
501806283312516 17 0
559755618233839 19 1
253673279319163 10 1
745815685342299 11 1
251710263962529 15 0
777195295276573 15 0
408579800634972 17 0
521840965162492 17 1
730678137312837 18 1
370007714721362 14 1
474595536466754 17 0
879365432938644 15 0
291785577961862 20 0
835878893889428 14 1
503562238579284 10 0
567569163005307 18 1
368949585722534 15 0
386435396601075 16 0

Sample Output 3

5329161389647368
1570154676347343
501806283312516
2665577865131167
1418696191276572
3952333977838189
982388401275366
1344764458281880
778587515356334
521840965162492
730678137312837
370007714721362
474595536466754
879365432938644
1631226710430574
1339441132468712
503562238579284
567569163005307
368949585722534
386435396601075