A - Tires

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

末尾が er または ist であるような文字列 S が与えられます。
S の末尾が er である場合は er を、 ist である場合は ist を出力してください。

制約

  • 2 \le |S| \le 20
  • S は英小文字のみからなる。
  • S の末尾は er または ist である。

入力

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

S

出力

答えを出力せよ。


入力例 1

atcoder

出力例 1

er

S="atcoder" の末尾は er です。


入力例 2

tourist

出力例 2

ist

入力例 3

er

出力例 3

er

Score : 100 points

Problem Statement

You are given a string S ending with er or ist.
If S ends with er, print er; if it ends with ist, print ist.

Constraints

  • 2 \le |S| \le 20
  • S consists of lowercase English letters.
  • S ends with er or ist.

Input

Input is given from Standard Input in the following format:

S

Output

Print the answer.


Sample Input 1

atcoder

Sample Output 1

er

S="atcoder" ends with er.


Sample Input 2

tourist

Sample Output 2

ist

Sample Input 3

er

Sample Output 3

er
B - 202<s>3</s>

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字と数字からなる文字列 S が入力されます。
S は 2023 で終わることが保証されます。
S の最後の文字を 4 に変更し、変更後の文字列を出力してください。

制約

  • S は英小文字と数字からなる長さ 4 以上 100 以下の文字列
  • S は 2023 で終わる。

入力

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

S

出力

答えを出力せよ。


入力例 1

hello2023

出力例 1

hello2024

hello2023 の最後の文字を 4 に変更すると、 hello2024 となります。


入力例 2

worldtourfinals2023

出力例 2

worldtourfinals2024

入力例 3

2023

出力例 3

2024

S が 2023 で終わることが保証されていますが、 S が 2023 そのものである場合もあります。


入力例 4

20232023

出力例 4

20232024

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters and digits.
S is guaranteed to end with 2023.
Change the last character of S to 4 and print the modified string.

Constraints

  • S is a string of length between 4 and 100, inclusive, consisting of lowercase English letters and digits.
  • S ends with 2023.

Input

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

S

Output

Print the answer.


Sample Input 1

hello2023

Sample Output 1

hello2024

Changing the last character of hello2023 to 4 yields hello2024.


Sample Input 2

worldtourfinals2023

Sample Output 2

worldtourfinals2024

Sample Input 3

2023

Sample Output 3

2024

S is guaranteed to end with 2023, possibly being 2023 itself.


Sample Input 4

20232023

Sample Output 4

20232024
C - Two Languages

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder 国の公用語は、高橋語と青木語の 2 つの言語です。

高橋語と青木語は、どちらもその言語に含まれる単語を表記するのに英小文字の一部を使います。 高橋語では長さ N の文字列 S に含まれる文字のみを使い、青木語では長さ M の文字列 T に含まれる文字のみを使います。

AtCoder 国の公用語に含まれる Q 個の単語 w _ 1,w _ 2,\ldots,w _ Q が与えられます。 それぞれの単語について、その単語に含まれる文字からその単語が次のうちどれに該当するか判定してください。

  • 高橋語の単語であることが確定する
  • 青木語の単語であることが確定する
  • どちらともいえない

制約

  • 1\le N\le26
  • 1\le M\le26
  • S は英小文字からなる長さ N の文字列
  • S に含まれる文字は先頭からアルファベット順で昇順に並んでいる
  • S に含まれる文字はすべて異なる
  • T は英小文字からなる長さ M の文字列
  • T に含まれる文字は先頭からアルファベット順で昇順に並んでいる
  • T に含まれる文字はすべて異なる
  • 1\le Q\le100
  • w _ i は英小文字からなる長さ 1 以上 100 以下の文字列 (1\le i\le Q)
  • w _ i は高橋語か青木語のどちらかの単語 (1\le i\le Q)
  • N,M,Q は整数

入力

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

N M
S
T
Q
w _ 1
w _ 2
\vdots
w _ Q

出力

Q 行にわたって出力せよ。 i 行目には、w _ i が高橋語の単語であることが確定するなら Takahashi 、青木語の単語であることが確定するなら Aoki 、どちらとも確定しないなら Unknown と出力せよ。


入力例 1

6 5
ahikst
aikot
5
asahi
okita
kiai
hash
it

出力例 1

Takahashi
Aoki
Unknown
Takahashi
Unknown

例えば、a, s, h, i はすべて高橋語で使われる文字で、h は青木語で使われる文字ではないので asahi は高橋語の単語であることが確定します。 よって、1 行目には Takahashi と出力してください。

i および t はどちらも高橋語でも青木語でも使われる文字なので it は高橋語の単語であるとも青木語の単語であるとも確定しません。 よって、5 行目には Unknown と出力してください。


入力例 2

7 6
ahiknst
ahikos
5
kioki
ohiki
tashi
nishi
kashi

出力例 2

Aoki
Aoki
Takahashi
Takahashi
Unknown

o は高橋語で使われる文字ではないので、はじめ 2 つの単語は青木語の単語であることが確定します。 よって、1 行目と 2 行目には Aoki と出力してください。

t や n は青木語で使われる文字ではないので、続く 2 つの単語は高橋語の単語であることが確定します。 よって、3 行目と 4 行目には Takahashi と出力してください。

はじめ 4 つの単語については、末尾が shi なら高橋語、末尾が ki なら青木語という法則がありますが、k, a, s, h, i はいずれも高橋語と青木語の両方で使われる文字なので kashi がどちらの言語の単語であるかを使われている文字から確定させることはできません。 よって、5 行目には Unknown と出力してください。


入力例 3

13 11
defghiqsvwxyz
acejmoqrtwx
15
qhsqzhd
jcareec
wwqxqew
wxqxwex
jxxrtwa
trtqjxe
sqyggse
xxqwxew
xewwxxw
wwqxwex
xqqxqwq
qxxexxe
teqeroc
eeeqqee
vxdevyy

出力例 3

Takahashi
Aoki
Unknown
Unknown
Aoki
Aoki
Takahashi
Unknown
Unknown
Unknown
Unknown
Unknown
Aoki
Unknown
Takahashi

Score : 200 points

Problem Statement

The AtCoder country has two official languages: Takahashi-go and Aoki-go.

Both Takahashi-go and Aoki-go use some lowercase English letters to write words in those languages. Takahashi-go uses only the characters contained in a string S of length N, and Aoki-go uses only the characters contained in a string T of length M.

You are given Q words w _ 1,w _ 2,\ldots,w _ Q that are in the official languages of the AtCoder country. For each word, determine which of the following applies based on the characters contained in that word:

  • It is confirmed to be a word in Takahashi-go
  • It is confirmed to be a word in Aoki-go
  • Neither can be determined

Constraints

  • 1\le N\le26
  • 1\le M\le26
  • S is a string of length N consisting of lowercase English letters.
  • The characters in S are arranged in alphabetical order.
  • All characters in S are distinct.
  • T is a string of length M consisting of lowercase English letters.
  • The characters in T are arranged in alphabetical order.
  • All characters in T are distinct.
  • 1\le Q\le100
  • w _ i is a string of length at least 1 and at most 100 consisting of lowercase English letters. (1\le i\le Q)
  • w _ i is a word in Takahashi-go or Aoki-go. (1\le i\le Q)
  • N,M,Q are integers.

Input

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

N M
S
T
Q
w _ 1
w _ 2
\vdots
w _ Q

Output

Print Q lines. The i-th line should contain Takahashi if it is confirmed that w _ i is a word in Takahashi-go, Aoki if it is confirmed to be a word in Aoki-go, and Unknown if neither can be determined.


Sample Input 1

6 5
ahikst
aikot
5
asahi
okita
kiai
hash
it

Sample Output 1

Takahashi
Aoki
Unknown
Takahashi
Unknown

For example, all of a, s, h, i are used in Takahashi-go, and h is not used in Aoki-go, so it is confirmed that asahi is a word in Takahashi-go. Thus, print Takahashi on the first line.

Both i and t are used in both Takahashi-go and Aoki-go, so it cannot be determined whether it is a word in Takahashi-go or Aoki-go. Thus, print Unknown on the fifth line.


Sample Input 2

7 6
ahiknst
ahikos
5
kioki
ohiki
tashi
nishi
kashi

Sample Output 2

Aoki
Aoki
Takahashi
Takahashi
Unknown

o is not used in Takahashi-go, so the first two words are confirmed to be words in Aoki-go. Thus, print Aoki on the first and second lines.

t and n are not used in Aoki-go, so the following two words are confirmed to be words in Takahashi-go. Thus, print Takahashi on the third and fourth lines.

For the first four words, there is a rule that words ending in shi are Takahashi-go, and words ending in ki are Aoki-go. However, all of k, a, s, h, i are used in both Takahashi-go and Aoki-go, so it is impossible to determine which language the word kashi belongs to based on the characters used. Thus, print Unknown on the fifth line.


Sample Input 3

13 11
defghiqsvwxyz
acejmoqrtwx
15
qhsqzhd
jcareec
wwqxqew
wxqxwex
jxxrtwa
trtqjxe
sqyggse
xxqwxew
xewwxxw
wwqxwex
xqqxqwq
qxxexxe
teqeroc
eeeqqee
vxdevyy

Sample Output 3

Takahashi
Aoki
Unknown
Unknown
Aoki
Aoki
Takahashi
Unknown
Unknown
Unknown
Unknown
Unknown
Aoki
Unknown
Takahashi
D - Mex

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の整数からなる数列 A=(A_1,\ldots,A_N) が与えられます。

A_1,\ldots,A_N に含まれない最小の非負整数を求めてください。

制約

  • 1 \leq N \leq 2000
  • 0 \leq A_i \leq 2000
  • 入力は全て整数である

入力

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

N
A_1 \ldots A_N

出力

答えを出力せよ。


入力例 1

8
0 3 2 6 2 1 0 0

出力例 1

4

非負整数は 0,1,2,3,4,\ldots と続きます。
0,1,2,3 は A に含まれ、4 は A に含まれないので、答えは 4 です。


入力例 2

3
2000 2000 2000

出力例 2

0

Score : 200 points

Problem Statement

You are given a sequence of length N consisting of integers: A=(A_1,\ldots,A_N).

Find the smallest non-negative integer not in (A_1,\ldots,A_N).

Constraints

  • 1 \leq N \leq 2000
  • 0 \leq A_i \leq 2000
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Print the answer.


Sample Input 1

8
0 3 2 6 2 1 0 0

Sample Output 1

4

The non-negative integers are 0,1,2,3,4,\ldots.
We have 0,1,2,3 in A, but not 4, so the answer is 4.


Sample Input 2

3
2000 2000 2000

Sample Output 2

0
E - Ladder Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

10^9 階建てのビルがあり、N 本のはしごがかかっています。
ビルの 1 階にいる高橋君ははしごを繰り返し使って(0 回でもよい)できるだけ高い階へ上りたいと考えています。
はしごには 1 から N までの番号がついており、はしご i は A_i 階と B_i 階を結んでいます。はしご i を利用すると A_i 階から B_i 階へ、または B_i 階から A_i 階へ双方向に移動することができますが、それ以外の階の間の移動は行うことはできません。
また、高橋君は同じ階での移動は自由に行うことができますが、はしご以外の方法で他の階へ移動することはできません。
高橋君は最高で何階へ上ることができますか?

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq 10^9
  • A_i \neq B_i
  • 入力はすべて整数

入力

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

N
A_1 B_1
A_2 B_2
\ldots
A_N B_N

出力

答えを出力せよ。


入力例 1

4
1 4
4 3
4 10
8 3

出力例 1

10

はしご 1 で 4 階に進み、はしご 3 で 10 階に進むことにより、10 階にたどり着くことができます。


入力例 2

6
1 3
1 5
1 12
3 5
3 12
5 12

出力例 2

12

入力例 3

3
500000000 600000000
600000000 700000000
700000000 800000000

出力例 3

1

他の階への移動ができない場合もあります。

Score : 300 points

Problem Statement

There is a 10^9-story building with N ladders.
Takahashi, who is on the 1-st (lowest) floor, wants to reach the highest floor possible by using ladders (possibly none).
The ladders are numbered from 1 to N, and ladder i connects the A_i-th and B_i-th floors. One can use ladder i in either direction to move from the A_i-th floor to the B_i-th floor or vice versa, but not between other floors.
Takahashi can freely move within the same floor, but cannot move between floors without using ladders.
What is the highest floor Takahashi can reach?

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq 10^9
  • A_i \neq B_i
  • All values in the input are integers.

Input

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

N
A_1 B_1
A_2 B_2
\ldots
A_N B_N

Output

Print an integer representing the answer.


Sample Input 1

4
1 4
4 3
4 10
8 3

Sample Output 1

10

He can reach the 10-th floor by using ladder 1 to get to the 4-th floor and then ladder 3 to get to the 10-th floor.


Sample Input 2

6
1 3
1 5
1 12
3 5
3 12
5 12

Sample Output 2

12

Sample Input 3

3
500000000 600000000
600000000 700000000
700000000 800000000

Sample Output 3

1

He may be unable to move between floors.

F - Reindeer and Sleigh 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

N 匹のトナカイと 1 個のソリがあります。i 番目のトナカイは重さが W_i で力は P_i です。

各トナカイについて、「ソリを引く」または「ソリに乗る」のいずれかを選びます。 ただし、ソリを引くトナカイの力の総和が、ソリに乗るトナカイの重さの総和以上でなければなりません。 最大で何匹トナカイをソリに乗せることができますか?

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1\leq T\leq 10^5
  • 1\leq N\leq 3\times 10^5
  • 1\leq W_i,P_i\leq 10^9
  • 入力は全て整数
  • 1 つの入力ファイルに含まれる N の総和は 3\times 10^5 以下

入力

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

N
W_1 P_1
W_2 P_2
\vdots
W_N P_N

出力

T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。


入力例 1

3
3
3 1
4 1
5 9
5
1000000000 1
1000000000 1
1000000000 1
1000000000 1
1000000000 1
10
133180711 458704923
531424946 225863856
141986070 637075158
500770732 289806469
502866767 408857335
559714289 569084545
287444582 992432993
559747907 753133304
432846188 949871298
727072164 756020367

出力例 1

2
0
6

1 つ目のテストケースについて、3 番目のトナカイがソリを引き、1 番目と 2 番目のトナカイがソリに乗ると、ソリを引くトナカイの力の総和は P_3=9、ソリに乗るトナカイの重さの総和は W_1+W_2=7 となるため条件を満たします。すべてのトナカイがソリに乗ることはできないため、求める答えは 2 です。

Score : 350 points

Problem Statement

There are N reindeer and one sled. The i-th reindeer has weight W_i and strength P_i.

For each reindeer, choose either "pull the sled" or "ride on the sled". Here, the total strength of the reindeer pulling the sled must be greater than or equal to the total weight of the reindeer riding on the sled. What is the maximum number of reindeer that can ride on the sled?

You are given T test cases. Solve each of them.

Constraints

  • 1\leq T\leq 10^5
  • 1\leq N\leq 3\times 10^5
  • 1\leq W_i,P_i\leq 10^9
  • All input values are integers.
  • The sum of N in one input file is at most 3\times 10^5.

Input

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N
W_1 P_1
W_2 P_2
\vdots
W_N P_N

Output

Output T lines. The i-th line should contain the answer for the i-th test case.


Sample Input 1

3
3
3 1
4 1
5 9
5
1000000000 1
1000000000 1
1000000000 1
1000000000 1
1000000000 1
10
133180711 458704923
531424946 225863856
141986070 637075158
500770732 289806469
502866767 408857335
559714289 569084545
287444582 992432993
559747907 753133304
432846188 949871298
727072164 756020367

Sample Output 1

2
0
6

For the 1st test case, if the 3rd reindeer pulls the sled and the 1st and 2nd reindeer ride on the sled, the total strength of the reindeer pulling the sled is P_3=9, and the total weight of the reindeer riding on the sled is W_1+W_2=7, satisfying the condition. Since not all reindeer can ride on the sled, the answer is 2.

G - Domino Covering XOR

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

H 行 W 列のマス目があります。 上から i 行目 (1\leq i\leq H)、左から j 列目 (1\leq j\leq W) のマスをマス (i,j) と呼ぶことにします。

マス (i,j)\ (1\leq i\leq H,1\leq j\leq W) には非負整数 A _ {i,j} が書かれています。

このマス目にドミノを 0 個以上置きます。 1 つのドミノは隣り合う 2 つのマス、つまり

  • 1\leq i\leq H,1\leq j\lt W に対するマス (i,j) とマス (i,j+1)
  • 1\leq i\lt H,1\leq j\leq W に対するマス (i,j) とマス (i+1,j)

のどれかに置くことができます。

ただし、同じマスに対して複数のドミノを置くことはできません。

ドミノの置き方に対して、置き方のスコアをドミノが置かれていないマスに書かれた整数すべてのビットごとの排他的論理和として定めます。

ドミノの置き方のスコアとしてありうる最大値を求めてください。

ビットごとの排他的論理和とは

非負整数 A, B のビットごとの排他的論理和 A \oplus B は、以下のように定義されます。

  • A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。

制約

  • 1\leq H
  • 1\leq W
  • HW\leq20
  • 0\leq A _ {i,j}\lt 2 ^ {60}\ (1\leq i\leq H,1\leq j\leq W)
  • 入力はすべて整数

入力

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

H W
A _ {1,1} A _ {1,2} \ldots A _ {1,W}
A _ {2,1} A _ {2,2} \ldots A _ {2,W}
\vdots
A _ {H,1} A _ {H,2} \ldots A _ {H,W}

出力

答えを出力せよ。


入力例 1

3 4
1 2 3 8
4 0 7 10
5 2 4 2

出力例 1

15

与えられたマス目は以下のようになります。

例えば、次のようにドミノを置くことでスコアを 15 とすることができます。

スコアを 16 以上にすることはできないため、15 を出力してください。


入力例 2

1 11
1 2 4 8 16 32 64 128 256 512 1024

出力例 2

2047

ドミノを 1 枚も置かないこともできます。


入力例 3

4 5
74832 16944 58683 32965 97236
52995 43262 51959 40883 58715
13846 24919 65627 11492 63264
29966 98452 75577 40415 77202

出力例 3

131067

Score : 425 points

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top (1\leq i\leq H) and the j-th column from the left (1\leq j\leq W).

Cell (i,j)\ (1\leq i\leq H,1\leq j\leq W) has a non-negative integer A_{i,j} written on it.

Let us place zero or more dominoes on the grid. A domino covers two adjacent cells, namely one of the following pairs:

  • cells (i,j) and (i,j+1) for 1\leq i\leq H,1\leq j\lt W;
  • cells (i,j) and (i+1,j) for 1\leq i\lt H,1\leq j\leq W.

No cell may be covered by more than one domino.

For a placement of dominoes, define its score as the bitwise XOR of all integers written in cells not covered by any domino.

Find the maximum possible score.

What is bitwise XOR?

For non-negative integers A and B, their bitwise XOR A \oplus B is defined as follows:

  • In binary, the 2^k bit (k \ge 0) of A \oplus B is 1 if exactly one of A and B has 1 in that bit, and 0 otherwise.
For example, 3 \oplus 5 = 6 (in binary, 011 \oplus 101 = 110).
For k non-negative integers p_1, p_2, p_3, \dots, p_k, their bitwise XOR is (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), which can be proved to be independent of the order of the operands.

Constraints

  • 1 \le H
  • 1 \le W
  • HW \le 20
  • 0 \le A_{i,j} < 2^{60} (1 \le i \le H,\ 1 \le j \le W)
  • All input values are integers.

Input

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

H W
A _ {1,1} A _ {1,2} \ldots A _ {1,W}
A _ {2,1} A _ {2,2} \ldots A _ {2,W}
\vdots
A _ {H,1} A _ {H,2} \ldots A _ {H,W}

Output

Output the answer.


Sample Input 1

3 4
1 2 3 8
4 0 7 10
5 2 4 2

Sample Output 1

15

The grid is as follows:

For example, the placement below yields a score of 15.

No placement achieves a score of 16 or higher, so output 15.


Sample Input 2

1 11
1 2 4 8 16 32 64 128 256 512 1024

Sample Output 2

2047

You may also choose to place no dominoes.


Sample Input 3

4 5
74832 16944 58683 32965 97236
52995 43262 51959 40883 58715
13846 24919 65627 11492 63264
29966 98452 75577 40415 77202

Sample Output 3

131067
H - Erasing Vertices 2

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 頂点 M 辺の単純無向グラフ(すなわち、自己辺も多重辺もない無向グラフ)が与えられます。i 本目の辺は頂点 U_i と頂点 V_i を結んでいます。頂点 i には正整数 A_i が書かれています。

あなたは、以下の操作を N 回繰り返します。

  • まだ削除されていない頂点 x を選び、「頂点 x 」と「頂点 x を端点に持つ辺全て」を削除する。この操作のコストは、頂点 x と辺で直接結ばれていて、かつまだ削除されていない頂点に書かれている整数の総和である。

N 回の操作全体のコストを、1 回ごとの操作におけるコストのうちの最大値として定めます。操作全体のコストとして取り得る値の最小値を求めてください。

制約

  • 1 \le N \le 2 \times 10^5
  • 0 \le M \le 2 \times 10^5
  • 1 \le A_i \le 10^9
  • 1 \le U_i,V_i \le N
  • 与えられるグラフは単純。
  • 入力は全て整数。

入力

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

N M
A_1 A_2 \dots A_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

出力

答えを出力せよ。


入力例 1

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

出力例 1

3

以下のように操作を行うことにより、N 回の操作のコストのうちの最大値を 3 にすることができます。

  • 頂点 3 を選ぶ。コストは A_1=3 である。
  • 頂点 1 を選ぶ。コストは A_2+A_4=3 である。
  • 頂点 2 を選ぶ。コストは 0 である。
  • 頂点 4 を選ぶ。コストは 0 である。

N 回の操作のコストのうちの最大値を 2 以下にすることはできないため、解は 3 です。


入力例 2

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

出力例 2

1199

Score : 500 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The i-th edge connects Vertices U_i and V_i. Vertex i has a positive integer A_i written on it.

You will repeat the following operation N times.

  • Choose a Vertex x that is not removed yet, and remove Vertex x and all edges incident to Vertex x. The cost of this operation is the sum of the integers written on the vertices directly connected by an edge with Vertex x that are not removed yet.

We define the cost of the entire N operations as the maximum of the costs of the individual operations. Find the minimum possible cost of the entire operations.

Constraints

  • 1 \le N \le 2 \times 10^5
  • 0 \le M \le 2 \times 10^5
  • 1 \le A_i \le 10^9
  • 1 \le U_i,V_i \le N
  • The given graph is simple.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \dots A_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M

Output

Print the answer.


Sample Input 1

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

Sample Output 1

3

By performing the operations as follows, the maximum of the costs of the N operations can be 3.

  • Choose Vertex 3. The cost is A_1=3.
  • Choose Vertex 1. The cost is A_2+A_4=3.
  • Choose Vertex 2. The cost is 0.
  • Choose Vertex 4. The cost is 0.

The maximum of the costs of the N operations cannot be 2 or less, so the solution is 3.


Sample Input 2

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

Sample Output 2

1199
I - Rotation Puzzle

Time Limit: 5 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

H 行 W 列のマス目があり、最初、1 以上 (H\times W) 以下の整数がちょうど 1 つずつ書き込まれています。
具体的には、1\leq i\leq H, 1\leq j\leq W について、上から i 行目かつ左から j 列目のマスには S_{i,j} が書き込まれています。
以下、上から i 行目かつ左から j 列目のマスをマス (i,j) と呼びます。

次の操作を 高々 20 回 (0 回でも良い)繰り返すことで、
任意の整数の組 (i,j) (1\leq i\leq H, 1\leq j\leq W) について、 マス (i,j) に ((i-1)\times W+j) が書き込まれている状態にできるか判定し、
できる場合は必要な操作回数の最小値を出力してください。
20 回以下でできない場合(何回操作を繰り返してもできない場合を含む)は -1 を出力してください。

操作:マス目から (H-1) \times (W-1) の長方形を選んで 180 度回転させる。
   より厳密には、整数 x,y (0 \leq x, y \leq 1) を選び、
   1 \leq i \leq H-1, 1 \leq j \leq W-1 をみたすすべての整数の組 (i,j) について同時に、
   マス (i+x,j+y) に書かれた整数をマス (H-i+x,W-j+y) に書かれた数に書き換える。

マス目に書き込まれている整数が条件をみたしていれば良く、書き込まれている向き等は考える必要がないことに注意してください。

制約

  • 3\leq H,W\leq 8
  • 1\leq S_{i,j}\leq H\times W
  • (i,j)\neq (i',j') ならば S_{i,j}\neq S_{i',j'}
  • 入力はすべて整数

入力

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

H W
S_{1,1} S_{1,2} \ldots S_{1,W}
S_{2,1} S_{2,2} \ldots S_{2,W}
\vdots
S_{H,1} S_{H,2} \ldots S_{H,W}

出力

問題文の条件をみたすために必要な操作回数の最小値を出力せよ。
ただし、20 回以下の操作で条件をみたすようにできないときは -1 を出力せよ。


入力例 1

3 3
9 4 3
2 1 8
7 6 5

出力例 1

2

次の順で操作を行うことで 2 回の操作で問題文の条件をみたすようにすることができます。

  • 左上の長方形を選び、操作を行う。すなわち x=0, y=0 を選んで操作を行う。
  • 右下の長方形を選び、操作を行う。すなわち x=1, y=1 を選んで操作を行う。

一方で 1 回以下の操作でみたすようにすることは不可能であるため、2 を出力します。


入力例 2

4 6
15 18 1 14 3 4
23 24 19 8 9 12
13 2 17 6 5 16
21 22 7 20 11 10

出力例 2

-1

20 回以下の操作で条件をみたすようにすることができないため、-1 を出力します。


入力例 3

4 6
1 4 13 16 15 18
21 20 9 12 23 10
17 14 5 6 3 2
11 22 7 24 19 8

出力例 3

20

入力例 4

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

出力例 4

0

Score: 550 points

Problem Statement

There is a grid with H rows and W columns. Initially, each integer from 1 to (H \times W) is written exactly once in the grid.
Specifically, for 1 \leq i \leq H and 1 \leq j \leq W, the cell at the i-th row from the top and the j-th column from the left contains S_{i,j}.
Below, let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

Determine if it is possible to reach a state where, for all pairs of integers (i,j) (1 \leq i \leq H, 1 \leq j \leq W),
the cell (i,j) contains the integer ((i-1) \times W + j) by repeating the following operation at most 20 times (possibly zero).
If it is possible, print the minimum number of operations required.
If it is impossible in 20 or fewer operations (including the case where it is impossible no matter how many times the operation is repeated), print -1.

Operation: Choose a rectangle of size (H-1) \times (W-1) from the grid and rotate it 180 degrees.
More precisely, choose integers x and y (0 \leq x, y \leq 1),
and for all pairs of integers (i,j) satisfying 1 \leq i \leq H-1 and 1 \leq j \leq W-1,
simultaneously replace the integer written in cell (i+x,j+y) with the number written in cell (H-i+x,W-j+y).

Note that it is only necessary for the integers written in the cells to satisfy the condition; the orientation in which they are written does not matter.

Constraints

  • 3 \leq H,W \leq 8
  • 1 \leq S_{i,j} \leq H \times W
  • If (i,j) \neq (i',j'), then S_{i,j} \neq S_{i',j'}
  • All input values are integers.

Input

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

H W
S_{1,1} S_{1,2} \ldots S_{1,W}
S_{2,1} S_{2,2} \ldots S_{2,W}
\vdots
S_{H,1} S_{H,2} \ldots S_{H,W}

Output

Print the minimum number of operations required to meet the conditions of the problem statement.
If it is impossible to satisfy the conditions with 20 or fewer operations, output -1.


Sample Input 1

3 3
9 4 3
2 1 8
7 6 5

Sample Output 1

2

Operating in the following order will satisfy the conditions of the problem statement in 2 operations.

  • Operate by choosing the rectangle in the top-left corner. That is, by choosing x=0 and y=0.
  • Operate by choosing the rectangle in the bottom-right corner. That is, by choosing x=1 and y=1.

On the other hand, it is impossible to satisfy the conditions with one or fewer operations, so print 2.


Sample Input 2

4 6
15 18 1 14 3 4
23 24 19 8 9 12
13 2 17 6 5 16
21 22 7 20 11 10

Sample Output 2

-1

It is impossible to satisfy the conditions with 20 or fewer operations, so print -1.


Sample Input 3

4 6
1 4 13 16 15 18
21 20 9 12 23 10
17 14 5 6 3 2
11 22 7 24 19 8

Sample Output 3

20

Sample Input 4

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

Sample Output 4

0