A - Credits

Time Limit: 1 sec / Memory Limit: 256 MB

配点 : 100

問題文

京都大学では今期、N 個の講義が開講されており、進級には K 単位以上取得する必要があります。

i 番目の講義に割り当てられている単位数は a_i です。 あなたは最小限の履修で進級したいと考えています。 いくつの授業を履修する必要があるか求めてください。

制約

  • 1 \leq N \leq 50
  • 1 \leq K \leq 1,000
  • 1 \leq a_i \leq 20
  • N, K, a_i は整数である。

入力

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

N K
a_1 a_2 ... a_N

出力

必要な履修数の最小値を求めよ。 全ての講義を履修しても単位が足りない場合、代わりに -1 を出力せよ。


入力例1

5 15
3 8 2 5 6

出力例1

3

例えば、1, 2, 4 番目の講義を履修すれば良いです。


入力例2

5 25
3 8 2 5 6

出力例2

-1

全ての講義を履修しても単位が足りません。


入力例3

4 20
1 1 20 19

出力例3

1

Score : 100 points

Problem Statement

Kyoto University offers N lectures and you need more than or equal to K credits to advance to the next grade. You can earn a_i credits by taking i-th lecture. You want to take as small number of lectures as possible to advance to the next grade. How many lectures do you need to take?

Constraints

  • 1 \leq N \leq 50
  • 1 \leq K \leq 1,000
  • 1 \leq a_i \leq 20
  • N, K, a_i are integers.

Input

Input is given from Standard Input in the following format:

N K
a_1 a_2 ... a_N

Output

Print the minimum number of lectures to advance to the next grade. If you can not advance to the next grade even by taking all the lectures, print -1 instead.


Sample Input 1

5 15
3 8 2 5 6

Sample Output 1

3

For example, you can adcance to the next grade with first, second, and fourth lectures.


Sample Input 2

5 25
3 8 2 5 6

Sample Output 2

-1

You can not advance to the next grade even by taking all the lectures.


Sample Input 3

4 20
1 1 20 19

Sample Output 3

1

Source Name

KUPC2017
B - Camphor Tree

Time Limit: 1 sec / Memory Limit: 256 MB

配点 100

問題文

京都大学の時計台の前には巨大なクスノキが生えています。 観察の結果、このクスノキの構造について次のことが分かっています。

  • ある正整数 N があり、クスノキには 2^N-1 個の分岐点が存在する。
  • 分岐点は 1 から 2^N-1 まで番号付けられている。
  • 1 \leq i \leq 2^{N-1}-1 を満たす各整数 i について以下のように枝がある。
    • 分岐点 i と分岐点 2i が枝で繋がっている。
    • 分岐点 i と分岐点 2i+1 が枝で繋がっている。
  • 上で述べられた条件を満たさない枝は存在しない。

例えば N=3 のときのクスノキの構造は下の図のようになっています.

クスノキ N=3

あなたは、このクスノキを登りたいと考えています。 クスノキの分岐点 S から T まで木登り可能であるとは、S=T であるか、または分岐点 S から分岐点 T まで通過する分岐点の番号が増大するように枝をたどっていくことができることを言います。 分岐点の番号 S と分岐点の番号 T が与えられるので S から T へ木登り可能かどうか判定してください。 また木登り可能であるときには、何本の枝を通過する必要があるかを答えてください。

制約

  • 1 \leq N \leq 25
  • 1 \leq S \leq 2^N-1
  • 1 \leq T \leq 2^N-1
  • N,S,T は整数である。

入力

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

N S T

出力

S から T へ木登り可能でないときは -1 を出力せよ。 S から T へ木登り可能であるときは通過する必要のある枝の本数を出力せよ。


入力例1

3 2 4

出力例1

1

分岐点 2 から 4 に木登り可能であり枝を 1 本通過するので 1 を出力します。


入力例2

3 7 1

出力例2

-1

入力例3

4 2 2

出力例3

0

Score : 100 points

Problem Statement

There is a huge kusunoki (camphor tree) in front of the clock tower of Kyoto University. It is reported that this kusunoki has the following structure.

  • There exists a positive integer N and the kusunoki has 2^N-1 branch points, which are numbered from 1 to 2^N-1.
  • For each integer i that holds 1 \leq i \leq 2^{N-1}-1, the kusunoki has branches according to the following rules.
    • Branch point i and 2i are connected with a branch.
    • Branch point i and 2i + 1 are connected with a branch.
  • There is no branch that does not hold the above rules.

For example, for N=3, the structure of the kusunoki is as follows.

Kusunoki N=3

You want to climb this kusunoki. You can climb from branch point S to T if and only if S=T or there exists a path of branches from S to T, where the numbers of branch points are in ascending order from S to T. Given two integers S and T, determine whether you can climb from branch point S to T. Also, if it is possible, answer the lowerst number of branches you need to climb.

Constraints

  • 1 \leq N \leq 25
  • 1 \leq S \leq 2^N-1
  • 1 \leq T \leq 2^N-1
  • N,S,T are integers.

Input

Input is given from Standard Input in the following format:

N S T

Output

If you can not climb from S to T, print -1. Otherwise, print the lowest number of branches you need to climb.


Sample Input 1

3 2 4

Sample Output 1

1

Since you can climb from branch point 2 to 4 through one branch, print 1.


Sample Input 2

3 7 1

Sample Output 2

-1

Sample Input 3

4 2 2

Sample Output 3

0

Source Name

KUPC2017
C - Best Password

Time Limit: 1 sec / Memory Limit: 256 MB

配点 : 100

問題文

京都大学のある建物にはパスワードを知っている者だけが認証を通り、入ることができます。

パスワードは英小文字からなる文字列であり、建物の利用者であるあなたにはこのパスワードが知らされています。

この認証システムは入力されたパスワードのハッシュ値を求め、そのハッシュ値を使って照合されるというシステムです。

長さ N の文字列 S のハッシュ値は、i 文字目を S_i として、以下の式で求められます。

A^1 \times C[S_1] + A^2 \times C[S_2] + ... + A^N \times C[S_N]

ただし A2 以上 10 以下の整数の定数であり、C[a]=1, C[b]=2, ..., C[z]=26 です。

あなたはとても忙しく、出来る限り短い入力で認証を済ませたいと考えています。

本来のパスワードと同じハッシュ値を持つような最短の文字列を求めてください。 条件を満たす最短の文字列が複数ある場合は、辞書順最大のものを求めてください。

制約

  • 2 \leq A \leq 10
    • A は整数である。
  • 1 \leq |S| \leq 1,000
    • S は英小文字からなる文字列である。

入力

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

A
S

出力

求める文字列を 1 行に出力せよ。


入力例1

2
kupc

出力例1

yzp

元の文字列のハッシュ値は

2^1 \times 11 + 2^2 \times 21 + 2^3 \times 16 + 2^4 \times 3 = 282

です。出力文字列のハッシュ値も同じく

2^1 \times 25 + 2^2 \times 26 + 2^3 \times 16 = 282

です。


入力例2

10
abcde

出力例2

utuvc

入力例3

4
zzz

出力例3

zzz

入力例4

9
kyotouniversityprogrammingcontest

出力例4

txxsxtwztwyrrsyyzwxyrtuzuxsvvswzs

ハッシュ値は非常に大きくなることがあります。

Score : 100 points

Problem Statement

One of the buildings in Kyoto University requires a password to enter.

This password consists of lowercase alphabets and you, one of those who use the building, know the password.

The authentication system of the building calculates a hash value from the password that is entered, and checks whether the hash value matches.

The hash value of string S of length N is calculated based on the following formula.

A^1 \times C[S_1] + A^2 \times C[S_2] + ... + A^N \times C[S_N]

A is an integer more than or equal to 2 and less than or equal to 10, and C[a]=1, C[b]=2, ..., C[z]=26.

You are so busy that you want to pass the authentication with as short password as possible.

Find the shortest password, the hash value of which is the same as that of the original password. If multiple passwords of the minimum length exist, find the lexicographically maximum one.

Constraints

  • 2 \leq A \leq 10
    • A is an integer.
  • 1 \leq |S| \leq 1,000
    • S consists of lowercase alphabets.

Input

Input is given from Standard Input in the following format:

A
S

Output

Print the password required above.


Sample Input 1

2
kupc

Sample Output 1

yzp

The hash value of the original string is

2^1 \times 11 + 2^2 \times 21 + 2^3 \times 16 + 2^4 \times 3 = 282.

The hash value of the output is also

2^1 \times 25 + 2^2 \times 26 + 2^3 \times 16 = 282.


Sample Input 2

10
abcde

Sample Output 2

utuvc

Sample Input 3

4
zzz

Sample Output 3

zzz

Sample Input 4

9
kyotouniversityprogrammingcontest

Sample Output 4

txxsxtwztwyrrsyyzwxyrtuzuxsvvswzs

The hash value is very large in some cases.


Source Name

KUPC2017
D - Sanmoku

Time Limit: 1 sec / Memory Limit: 256 MB

配点 : 200

問題文

NN 列のタイルの各マスに、それぞれ 10^9 以下の正整数を 1 つずつ書いていきます。 ただし、全てのマスに正整数を書き終わった後に以下の条件を満たしている必要があります。

  • どの縦、横、斜めに連続する 3 つのマスを選んでも、2 種類以上の正整数が含まれている。

あなたは、タイルに書く正整数の最大値 K をなるべく小さくしたいと考えています。 K の最小値を求めて下さい。また、K が最小値をとるような盤面の状態の個数を 10^9 + 7 で割った余りも求めて下さい。

制約

  • N は整数である。
  • 1 \leq N \leq 200

入力

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

N

出力

K の最小値と、K が最小値をとるような盤面の状態の個数を 10^9 + 7 で割った余りを空白区切りで 1 行に出力せよ。


入力例1

1

出力例1

1 1

連続する 3 マスがないので全て 1 で盤面を埋めることができ、盤面の状態は 1 通りである。


入力例2

2

出力例2

1 1

入力例3

4

出力例3

2 18

Score : 200 points

Problem Statement

You want to write a positive integer less than or equal to 10^9 in each cell of a tile with N rows and N columns. The tile must hold the following condition after you have written all positive integers.

  • For any 3 consecutive cells that are aligned vertically, horizonally, or diagonally, the cells must contain at least 2 different positive integers.

You want to make the maximum integer K in the tile as small as possible. Find the minimum K and the number of the distinct states of tiles where K is the minimum value, modulo 10^9 + 7.

Constraints

  • N is an integer.
  • 1 \leq N \leq 200

Input

Input is given from Standard Input in the following format:

N

Output

Print the minimum K, and the number of the distinct states of tiles where K is the minimum value modulo 10^9 + 7, with a single space in between.


Sample Input 1

1

Sample Output 1

1 1

Since there are no 3 consecutive cells, you can fill every cell with 1 and the number of different states are 1.


Sample Input 2

2

Sample Output 2

1 1

Sample Input 3

4

Sample Output 3

2 18

Source Name

KUPC2017
E - Treasure Hunt

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200

問題文

n 個の宝箱と m 個の鍵があります。

宝箱はそれぞれ 1 から n まで番号付けられており、i 番目の宝箱を開けると価値 v_i の宝石が 1 個得られます。

また、鍵はそれぞれ 1 から m まで番号付けられており、i 番目の鍵は x_i 番目の宝箱か y_i 番目の宝箱のいずれか一方を開けることができます。

ただし、同じ宝箱を複数回開けても得られる宝石は 1 個です。

得られる宝石の合計価値の最大値を求めてください。

制約

  • 入力は全て整数である
  • 1 \leq n \leq 10^5
  • 1 \leq m \leq 2 \times 10^5
  • 1 \leq v_i \leq 10^{12} (1 \leq i \leq n)
  • 1 \leq x_i, y_i \leq n (1 \leq i \leq m)

入力

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

n m
v_1 v_2 ... v_n
x_1 y_1
x_2 y_2
:
x_m y_m

出力

得られる宝石の合計価値の最大値を 1 行で出力せよ。


入力例1

5 4
20 10 5 8 6
1 2
2 3
3 1
4 5

出力例1

43

以下の場合に得られる宝石の合計価値が 43 となり、これが最大です。

  • 1 番目の鍵で 1 番目の宝箱を開ける
  • 2 番目の鍵で 2 番目の宝箱を開ける
  • 3 番目の鍵で 3 番目の宝箱を開ける
  • 4 番目の鍵で 4 番目の宝箱を開ける

入力例2

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

出力例2

39

入力例3

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

出力例3

30

入力例4

4 4
20 17 10 1
1 2
1 2
3 3
3 4

出力例4

48

複数の鍵が同じ組の宝箱を開けられる場合や、1 種類の宝箱しか開けられない鍵が存在する場合があります。


入力例5

23 20
683654281944 786549938314 108776810532 691131809160 942432243130 63770179509 238399760640 777689878960 646058383313 576573571139 18835030915 479397445387 877859338277 965037937502 199599909896 785875134824 682649947008 167867064215 956377730283 681772713017 633843536114 123843426658 384215401230
4 10
17 19
9 19
20 9
12 19
10 18
13 21
23 19
7 21
11 15
16 19
15 8
8 2
19 10
22 21
14 23
3 19
1 12
6 9
2 10

出力例5

11387100771264

入力および出力が 32 bit整数型に収まらない場合があります。

Score : 200 points

Problem Statement

There are n treasure boxes and m keys.

The treasure boxes are numbered from 1 to n and treasure box i contains a jewel with value v_i.

The keys are numbered from 1 to m and key i can open either treasure box x_i or y_i. (You can not open both of the treasure boxes only using key i.)

You can only get 1 jewel in total even if you open the same treasure box several times.

Find the maximum sum of the value of the jewels you can obtain.

Constraints

  • All input values are integers.
  • 1 \leq n \leq 10^5
  • 1 \leq m \leq 2 \times 10^5
  • 1 \leq v_i \leq 10^{12} (1 \leq i \leq n)
  • 1 \leq x_i, y_i \leq n (1 \leq i \leq m)

Input

Input is given from Standard Input in the following format:

n m
v_1 v_2 ... v_n
x_1 y_1
x_2 y_2
:
x_m y_m

Output

Find the maximum sum of the value of the jewels you can obtain.


Sample Input 1

5 4
20 10 5 8 6
1 2
2 3
3 1
4 5

Sample Output 1

43

You can obtain the maximum total value of 43 as follows.

  • Use key 1 for treasure box 1
  • Use key 2 for treasure box 2
  • Use key 3 for treasure box 3
  • Use key 4 for treasure box 4

Sample Input 2

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

Sample Output 2

39

Sample Input 3

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

Sample Output 3

30

Sample Input 4

4 4
20 17 10 1
1 2
1 2
3 3
3 4

Sample Output 4

48

Multiple keys can open the same set of treasure boxes, and some keys can open only one kind of treasure box.


Sample Input 5

23 20
683654281944 786549938314 108776810532 691131809160 942432243130 63770179509 238399760640 777689878960 646058383313 576573571139 18835030915 479397445387 877859338277 965037937502 199599909896 785875134824 682649947008 167867064215 956377730283 681772713017 633843536114 123843426658 384215401230
4 10
17 19
9 19
20 9
12 19
10 18
13 21
23 19
7 21
11 15
16 19
15 8
8 2
19 10
22 21
14 23
3 19
1 12
6 9
2 10

Sample Output 5

11387100771264

Inputs or outputs may overflow 32-bit integers.


Source Name

KUPC2017
F - 575

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200

問題文

数列 s に対して、その数列を構成する数を 0 個以上取り除き、残った数を元の順番で並べて得られる数列を s の部分列と呼びます。 たとえば、(4, 2, 1)(7, 4, 3, 2, 1)(空列)(7, 4, 3, 2, 1) の部分列ですが、(1, 2)(7, 4, 3, 2, 1) の部分列ではありません。

長さ n の数列 s について、次の条件を満たす空でない数列 a, b, c が存在するとき、数列 s を五七五列であるといいます。

  • a, b, c を連結した数列は (1, 2, ..., n) の順列である。
  • min_i(a_i) < min_i(b_i) < min_i(c_i)
  • Σs_{a_i} = 5
  • Σs_{b_i} = 7
  • Σs_{c_i} = 5

たとえば、数列 ex=(ex_1, ex_2, ex_3, ex_4)=(5, 3, 5, 4) は五七五列ですが、(5, 5, 7) は五七五列ではありません。ex については a=(1), b=(2, 4), c=(3)3 つの数列が五七五列の条件を満たします。

項数 N の数列 x=(x_1, x_2, ..., x_N) が与えられます。各 x_i2 \leq x_i \leq 7 を満たします。 この数列 x から、五七五列である部分列を 1 つずつ取り除くとき、最大でいくつの五七五列を取り除けるか求めてください。

制約

  • 1 \leq N \leq 100
  • 2 \leq x_i \leq 7
  • N, x_i は整数である。

入力

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

N
x_1 x_2 ... x_N

出力

取り除ける五七五列の最大個数を 1 行で出力せよ。


入力例1

5
2 3 5 4 3

出力例1

1

(2, 3, 5, 4, 3) は五七五列です。a=(1, 5), b=(2, 4), c=(3)3 つの数列が五七五列の条件を満たします。


入力例2

10
5 6 2 3 5 5 5 7 5 3

出力例2

2

まず、x の第 1, 3, 5, 6 項からなる (5, 2, 5, 5) の五七五列が取り除けます。 (5, 2, 5, 5) については、例えば a=(1), b=(2, 4), c=(3)3 つの数列が五七五列の条件を満たします。

x から第 1, 3, 5, 6 項を取り除いた残りの列は (6, 3, 5, 7, 5, 3) となります。 次に、残りの列の第 3, 4, 5 項からなる (5, 7, 5) の五七五列が取り除けます。


入力例3

5
6 6 6 6 6

出力例3

0

入力例4

9
5 3 2 2 7 3 5 4 3

出力例4

2

入力例5

8
5 5 4 3 5 5 4 3

出力例5

2

入力例6

22
2 3 4 5 6 7 6 5 4 3 2 2 3 4 5 6 7 6 5 4 3 2

出力例6

3

Score : 200 points

Problem Statement

A subsequence is a sequence that can be derived from another sequence by deleting some (incuding 0) elements without changing the order of the remaining elements. For example, (4, 2, 1), (7, 4, 3, 2, 1), and (empty) are subsequences of (7, 4, 3, 2, 1), but (1, 2) is not.

A sequence s of length n is called "575-sequence" if there exist numerical sequences a, b, and c that satisfy the following constraints.

  • A sequence made by concatenating a, b, and c is a permutation of (1, 2, ..., n).
  • min_i(a_i) < min_i(b_i) < min_i(c_i)
  • Σs_{a_i} = 5
  • Σs_{b_i} = 7
  • Σs_{c_i} = 5

For example, ex=(ex_1, ex_2, ex_3, ex_4)=(5, 3, 5, 4) is a 575-sequence, but (5, 5, 7) is not. For ex, a=(1), b=(2, 4), and c=(3) satisfy the above constraints.

You are given a sequence x=(x_1, x_2, ..., x_N) of length N. Each term x_i satisfies 2 \leq x_i \leq 7. How many 575-sequences can you remove one by one from x?

Constraints

  • 1 \leq N \leq 100
  • 2 \leq x_i \leq 7
  • N, x_i are integers

Input

Input is given from Standard Input in the following format:

N
x_1 x_2 ... x_N

Output

Print the maximum number of 575-sequences you can remove from x.


Sample Input 1

5
2 3 5 4 3

Sample Output 1

1

(2, 3, 5, 4, 3) is a 575-sequence. a=(1, 5), b=(2, 4), and c=(3) satisfy the constraints of 575-sequence.


Sample Input 2

10
5 6 2 3 5 5 5 7 5 3

Sample Output 2

2

Firstly, you can remove a 575-sequence (5, 2, 5, 5), which consists of the first, third, fifth, and sixth terms of x. For (5, 2, 5, 5), for example, a=(1), b=(2, 4), and c=(3) satisfy the constraints.

The remaining sequence, where the first, third, fifth, and sixth terms are removed from x is (6, 3, 5, 7, 5, 3). You can remove a 575-sequence (5, 7, 5), which consists of the third, fourth, and fifth terms of the remaining sequence.


Sample Input 3

5
6 6 6 6 6

Sample Output 3

0

Sample Input 4

9
5 3 2 2 7 3 5 4 3

Sample Output 4

2

Sample Input 5

8
5 5 4 3 5 5 4 3

Sample Output 5

2

Sample Input 6

22
2 3 4 5 6 7 6 5 4 3 2 2 3 4 5 6 7 6 5 4 3 2

Sample Output 6

3

Source Name

KUPC2017
G - encode/decode 2017

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300

問題文

あなたは以下のようなゲームに参加します。

  1. N = 100 頂点 M (= N-1 = 99) 辺からなる木 T と整数 X が与えられる。T の頂点には 1,2,...,N の番号がついており、各 i (1 \leq i \leq M) について頂点 a_{i} と頂点 b_{i} の間に辺がある。
  2. あなたは、多重辺や自己辺ができないように、T に辺を付け加えることを 0 回以上繰り返してグラフ G を作る。ここで A 本の辺を付け加えたとする。
  3. G から T にあった辺が消え、頂点番号が付け替わったグラフ G' が生成される。G'N = 100 頂点 A 辺からなるグラフで、G' の頂点には 1,2,...,N の番号がついており、各 i (1 \leq i \leq A) について頂点 c_{i} と頂点 d_{i} の間に辺がある。
  4. あなたの記憶から木 T とグラフ G と整数 X の情報が消える。
  5. あなたはグラフ G' を見て、整数 Y を宣言する。X = Y となれば成功となる。

あなたはどのような木 T と整数 X が与えられてもゲームが成功できるようにしたいと思っています。 木 T と整数 X が与えられたとき、辺の付け加え方を求め、そこから手順 3 によって生成されたグラフ G' が与えられたとき整数 Y を求めるプログラムを作成してください。

制約

  • N = 100
  • M = 99
  • T は木である
  • 1 \leq a_{i}, b_{i} \leq N (1 \leq i \leq M)
  • 0 \leq X \leq 10^{18}
  • 0 \leq A \leq {}_NC_2-M = 4,851
  • 1 \leq c_{i}, d_{i} \leq N (1 \leq i \leq A)
  • N, M, A, a_{i}, b_{i}, c_{i}, d_{i}, X は全て整数である

入出力

この問題には encode フェーズと decode フェーズがあり、それぞれ独立にプログラムが実行される。

ただし、encode フェーズとは木 T と整数 X が与えられたとき、辺の付け加え方を求めることに該当し、deocde フェーズとは手順 3 によって生成されたグラフ G' が与えられたとき整数 Y を求めることに該当する。

入力 (encode フェーズ)

encode フェーズにおいて入力は以下の形式で標準入力から与えられる。

1 行目は文字列 encode が与えられる。

encode
N M
a_{1} b_{1}
a_{2} b_{2}
:
a_{M} b_{M}
X

出力 (encode フェーズ)

出力は A+1 行からなる。

最初の 1 行に A を出力し、続く A 行の i (1 \leq i \leq A) 行目に、i 回目に付け加える辺の端点の頂点番号を、空白を区切りとして出力せよ。

ただし、encode フェーズの出力が次に示すいずれかの場合には不正解となり、decode フェーズは実行されない。

  • 出力された辺を全て木 T に付け加えたグラフが多重辺や自己辺を含む場合
  • 出力された辺の端点の頂点番号が 1 以上 N 以下でない場合

入力 (decode フェーズ)

decode フェーズにおいて入力は以下の形式で標準入力から与えられる。

1 行目は文字列 decode が与えられる。

decode
N A
c_{1} d_{1}
c_{2} d_{2}
:
c_{A} d_{A}

出力 (decode フェーズ)

Y の値を 1 行で出力せよ。 X = Y であった場合に限り正解となる。

ジャッジ

ジャッジは以下の手順で行われる。

  1. 提出されたプログラムのプロセスを encode 用と decode 用として2つ立ち上げる。
  2. encode 用のプロセスに encode フェーズの入力を与える。ただし、EOF は与えない。
  3. encode 用のプロセスから encode フェーズの適切な出力があり、かつ encode 用のプロセスが終了するまで待機する。
  4. 出力された辺を全て木 T に付け加えたグラフが多重辺や自己辺を含む場合や、出力された辺の端点の頂点番号が 1 以上 N 以下でない場合は誤答とする。
  5. decode 用のプロセスに decode フェーズの入力を与える。ただし、EOF は与えない。
  6. decode 用のプロセスから decode フェーズの適切な出力があり、かつdecode 用のプロセスが終了するまで待機する。
  7. X = Y の場合に限り正答、そうでなければ誤答とする。

また、出力のフォーマットが不正な場合も誤答とする。


入力例1 (encode フェーズ)

encode
100 99
49 74
50 84
78 91
12 14
9 62
54 77
47 88
29 55
52 53
3 53
53 63
33 95
9 57
44 48
3 13
3 73
1 49
62 63
48 53
55 94
50 60
89 95
57 64
75 96
7 48
41 99
44 79
21 94
13 50
42 82
1 16
22 88
19 34
63 87
1 36
14 58
18 56
33 82
12 37
55 84
87 96
12 55
4 76
64 68
38 52
40 50
38 59
47 75
17 32
18 83
20 63
76 92
54 71
34 59
16 89
39 94
2 98
11 85
24 60
28 76
46 70
19 23
41 46
36 40
68 93
15 37
2 68
82 90
4 26
45 90
28 59
43 94
10 44
16 54
65 97
41 51
10 27
96 97
10 86
52 91
5 44
18 28
32 99
67 84
67 100
46 80
55 72
18 80
69 71
6 43
25 71
30 96
8 57
11 88
80 81
19 61
30 35
8 31
42 66
382174891210833608

出力例1 (encode フェーズ)

2
1 2
2 4

入力例1 (decode フェーズ)

decode
100 2
49 33
35 49

G' の頂点番号は元の木 T と異なるものになる可能性があることに注意せよ。

出力例1 (decode フェーズ)

382174891210833608

Score : 300 points

Problem Statement

You are playing the following game.

  1. You are given a tree with N = 100 vertices and M (= N-1 = 99) edges, and an integer X. The vertices of T are numbered from 1 to N. For each i (1 \leq i \leq M), vertex a_{i} and b_{i} are connected with an edge.
  2. You make graph G by adding A (>= 0) edges to tree T one by one such that G does not have multiple edges and self-loops.
  3. The edges in G which also exist in T disappear and G is renamed G' after the numbers of the vertices in G are permutated. G' has N = 100 vertices and A edges. The vertices in G' are numbered from 1 to N, and for each i (1 \leq i \leq A), c_{i} and d_{i} are connected with an edge.
  4. The information on tree T, graph G, and integer X disappear from your memory.
  5. You look at graph G' and declare an integer Y. If X = Y, you win.

You want to win the above game even if any tree T and integer X are given. Given tree T and integer X, find how to add A edges to T, and then given the generated G', find integer Y to win the game.

Constraints

  • N = 100
  • M = 99
  • T is a tree.
  • 1 \leq a_{i}, b_{i} \leq N (1 \leq i \leq M)
  • 0 \leq X \leq 10^{18}
  • 0 \leq A \leq {}_NC_2-M = 4,851
  • 1 \leq c_{i}, d_{i} \leq N (1 \leq i \leq A)
  • N, M, A, a_{i}, b_{i}, c_{i}, d_{i}, X are integers.

Input and Output

This problem has encode and decode phases, each of which is executed independently.

In encode phase, you take tree T and integer X, and find how to add edges to tree T. In decode phase, you take the generated graph G', and find integer Y.

Input (encode phase)

In encode phase, input is given from Standard Input in the following format:

String encode is given on the first line.

encode
N M
a_{1} b_{1}
a_{2} b_{2}
:
a_{M} b_{M}
X

Output (encode phase)

In encode phase, you must print A+1 lines.

Print A on the first line. Then, print the vertices of the i-th (1 \leq i \leq A) added edge on the following i-th line, a single space in between.

Input (decode phase)

In decode phase, input is given from Standard Input in the following format:

String decode is given on the first line.

decode
N A
c_{1} d_{1}
c_{2} d_{2}
:
c_{A} d_{A}

Output (decode phase)

Print Y. If X = Y, your output is correct.

Judge

The judging procedure is run in the following steps.

  1. Two processes are launched to run the submitted program for the encode and decode phases.
  2. The input for the encode phase is given to the process for encoding. Note that EOF is not given.
  3. Wait until the process for encoding prints the output of the encode phase and the process for encoding exits completely.
  4. If graph G, which is generated by the output of the encode phase, contains multiple edges and self-loops or the numbers of the vertices is not in the range: [1, N], the answer is wrong.
  5. The output for the decode phase is given to the process for decoding. Note that EOF is not given.
  6. Wait until the process for decoding prints the output of the decode phase and the process for decoding exits completely.
  7. If X = Y, your program is correct, otherwise, wrong.

Note that if the formats of the outputs are invalid, the submitted program is also judged as wrong.


Sample Input 1 (encode phase)

encode
100 99
49 74
50 84
78 91
12 14
9 62
54 77
47 88
29 55
52 53
3 53
53 63
33 95
9 57
44 48
3 13
3 73
1 49
62 63
48 53
55 94
50 60
89 95
57 64
75 96
7 48
41 99
44 79
21 94
13 50
42 82
1 16
22 88
19 34
63 87
1 36
14 58
18 56
33 82
12 37
55 84
87 96
12 55
4 76
64 68
38 52
40 50
38 59
47 75
17 32
18 83
20 63
76 92
54 71
34 59
16 89
39 94
2 98
11 85
24 60
28 76
46 70
19 23
41 46
36 40
68 93
15 37
2 68
82 90
4 26
45 90
28 59
43 94
10 44
16 54
65 97
41 51
10 27
96 97
10 86
52 91
5 44
18 28
32 99
67 84
67 100
46 80
55 72
18 80
69 71
6 43
25 71
30 96
8 57
11 88
80 81
19 61
30 35
8 31
42 66
382174891210833608

Sample Output 1 (encode phase)

2
1 2
2 4

Sample Input 1 (decode phase)

decode
100 2
49 33
35 49

Note that the numbers of the vertices in G' may be different from the ones of T.

Sample Output 1 (decode phase)

382174891210833608

Source Name

KUPC2017
H - Make a Potion

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300

問題文

n 種類の液体を調合して 1 つのポーションを作ろうとしています。

i 種類目 (1 \leq i \leq n) の液体は体積が v_i あります。

液体をそれぞれ体積 w_1, w_2, ..., w_n 使うと、ポーションの効力は Σw_i \times h_i になります。

ただし、使う体積は整数でなければなりません。

さらに、m 個の条件があり、i 番目 (1 \leq i \leq m) の条件は以下の通りです。

  • a_i 種類目の液体を体積 x_i 以上使うなら、b_i 種類目の液体を体積 y_i 以上使わなければならない

条件を満たすように液体を使ったときのポーションの効力の最大値を求めてください。

制約

  • 入力は全て整数である
  • 1 \leq n \leq 1,000
  • 1 \leq m \leq 2,000
  • 1 \leq v_i \leq 10^6 (1 \leq i \leq n)
  • -10^6 \leq h_i \leq 10^6 (1 \leq i \leq n)
  • 1 \leq a_i, b_i \leq n (1 \leq i \leq m)
  • 0 \leq x_i \leq v_{a_i} (1 \leq i \leq m)
  • 0 \leq y_i \leq v_{b_i} (1 \leq i \leq m)
  • 同じ条件は複数回与えられない

入力

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

n m
v_1 v_2 ... v_n
h_1 h_2 ... h_n
a_1 x_1 b_1 y_1
a_2 x_2 b_2 y_2
:
a_m x_m b_m y_m

出力

ポーションの効力の最大値を標準出力に 1 行で出力せよ。


入力例1

2 2
1000 1800
1 -10
1 200 2 10
1 801 2 1000

出力例1

700

1 種類目の液体を体積 8002 種類目の液体を体積 10 使ったときの効力が最大です。


入力例2

1 4
500
-3
1 0 1 100
1 50 1 300
1 300 1 400
1 401 1 410

出力例2

-1200

1 種類目の液体を少なくとも体積 400 使わなければなりません。


入力例3

6 4
100 30 40 50 60 70
3 -5 2 -1 20 -10
1 20 2 20
3 11 2 25
2 24 4 10
3 30 1 80

出力例3

1445

入力例4

1 1
1000000
1000000
1 0 1 0

出力例4

1000000000000

答えが 32 bit整数型に収まらない場合があります。

Score : 300 points

Problem Statement

You are compounding n kinds of liquid into a potion.

The volume of liquid i (1 \leq i \leq n) is v_i.

When you use i-th (1 \leq i \leq n) liquid of volume w_i (0 \leq w_i \leq v_i) for each i, you earn the effectiveness of $Σw_i \times h_i.

Note that each volume you use must be an integer.

You also have m conditions and i-th condition (1 \leq i \leq m) is as follows.

  • If you use liquid a_i of volume more than or equal to x_i, you must also use liquid b_i of volume more than or equal to y_i.

Find the maximum effectiveness of the potion you can obtain within the above conditions.

Constraints

  • All input values are integers.
  • 1 \leq n \leq 1,000
  • 1 \leq m \leq 2,000
  • 1 \leq v_i \leq 10^6 (1 \leq i \leq n)
  • -10^6 \leq h_i \leq 10^6 (1 \leq i \leq n)
  • 1 \leq a_i, b_i \leq n (1 \leq i \leq m)
  • 0 \leq x_i \leq v_{a_i} (1 \leq i \leq m)
  • 0 \leq y_i \leq v_{b_i} (1 \leq i \leq m)
  • The same condition is given at most once.

Input

Input is given from Standard Input in the following format:

n m
v_1 v_2 ... v_n
h_1 h_2 ... h_n
a_1 x_1 b_1 y_1
a_2 x_2 b_2 y_2
:
a_m x_m b_m y_m

Output

Print the maximum effectiveness of the potion you can obtain within the above conditions.


Sample Input 1

2 2
1000 1800
1 -10
1 200 2 10
1 801 2 1000

Sample Output 1

700

You can get the maximum effectiveness by using liquid 1 of volume 800 and liquid 2 of volume 10.


Sample Input 2

1 4
500
-3
1 0 1 100
1 50 1 300
1 300 1 400
1 401 1 410

Sample Output 2

-1200

You must use liquid 1 of volume at least 400.


Sample Input 3

6 4
100 30 40 50 60 70
3 -5 2 -1 20 -10
1 20 2 20
3 11 2 25
2 24 4 10
3 30 1 80

Sample Output 3

1445

Sample Input 4

1 1
1000000
1000000
1 0 1 0

Sample Output 4

1000000000000

Some answers overflow 32-bit integers.


Source Name

KUPC2017
I - Activate It!!

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300

問題文

n 個の魔法石が左右一列に並んでいます。

はじめはどの魔法石も活性化されていません。

m 種類の魔法があり、i 種類目の魔法を詠唱すると、左から l_i, l_i+1, ..., r_i 番目の魔法石のうち、活性化されていない魔法石が全て活性化されます。

ただし、左から x_1, x_2, ..., x_k 番目の魔法石全てが活性化されると、これ以上魔法を詠唱しても新たに魔法石が活性化されることはありません。

これらの魔法を 1 つずつ好きな順番で詠唱し、できるだけ多くの魔法石を活性化させたいです。

活性化できる魔法石の個数の最大値を求めてください。

制約

  • 入力は全て整数である
  • 1 \leq n \leq 10^5
  • 1 \leq m \leq 10^5
  • 1 \leq k \leq n
  • 1 \leq l_i \leq r_i \leq n
  • 1 \leq x_1 < x_2 < ... < x_k \leq n
  • (l_i, r_i) (i=1,...,m) たちは互いに異なる

入力

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

n m k
x_1 x_2 ... x_k
l_1 r_1
l_2 r_2
:
l_m r_m

出力

活性化できる魔法石の個数の最大値を一行で出力せよ。


入力例1

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

出力例1

7

以下の順に魔法を詠唱すると全ての魔法石を活性化できます。

  • 2 番目の魔法を詠唱すると、新たに 3, 4 番目の魔法石が活性化される
  • 1 番目の魔法を詠唱すると、新たに 1, 2 番目の魔法石が活性化される
  • 3 番目の魔法を詠唱すると、新たに 5, 6, 7 番目の魔法石が活性化される

入力例2

10 4 1
6
1 2
4 5
2 7
5 10

出力例2

9

入力例3

6 1 2
2 6
3 4

出力例3

2

Score : 300 points

Problem Statement

There are n magic stones aligned in a line from left to right.

At first, no magic stones are activated.

You use m kinds of magic. If you use magic i, all the l_i-th, l_i+1-th, ..., r_i-th magic stones from the left get activated. ( Magic stones which are already activated also keep activated. )

However, once all the x_1-th, x_2-th, ..., x_k-th magic stones are activated, no more magic stones get activated even if you use more magic.

You want to activate as many magic stones as possible by using each magic exactly once in any order you want.

Find the maximum number of magic stones you can activate.

Constraints

  • All input values are integers.
  • 1 \leq n \leq 10^5
  • 1 \leq m \leq 10^5
  • 1 \leq k \leq n
  • 1 \leq l_i \leq r_i \leq n
  • 1 \leq x_1 < x_2 < ... < x_k \leq n
  • (l_i, r_i) (i=1,...,m) is distinct from each other.

Input

Input is given from Standard Input in the following format:

n m k
x_1 x_2 ... x_k
l_1 r_1
l_2 r_2
:
l_m r_m

Output

Print the maximum number of magic stones you can activate.


Sample Input 1

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

Sample Output 1

7

You can activate all the magic stones by using magic in the following order.

  • Use the second magic, and the third and fourth magic stones get activated.
  • Use the first magic, and the first and second magic stones get activated.
  • Use the third magic, and the fifth, sixth, and seventh magic stones get activated.

Sample Input 2

10 4 1
6
1 2
4 5
2 7
5 10

Sample Output 2

9

Sample Input 3

6 1 2
2 6
3 4

Sample Output 3

2

Source Name

KUPC2017
J - Paint Red and Make Graph

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400

問題文

HW 列の盤面が目の前にあります。 各マスは最初は白か黒のいずれかの色で塗られており、a_{i,j}. のときは ij 列目のマスは白に、# のときは黒に塗られています。 あなたは、以下の条件を満たすように白のマスの一部を赤に塗り替えたいと考えています。

  • 全ての列と行には少なくともひとつの赤マスがある。
  • 以下のようにグラフを構成したとき、そのグラフは連結である。
    • 全ての赤マスに対して、対応する頂点を作る。 (このとき、グラフの頂点数と赤マスの数は等しい。)
    • 同じ行または同じ列にあるマスに対応する頂点同士に辺を張る。

以上の条件を満たすように赤マスに塗り替えるとき、赤マスに塗り替える白マスの数の最小値を求めてください。 また、赤マスに塗り替える白マスの数が最小となるような塗り方の個数を 10^9 + 7 で割った余りを求めてください。

制約

  • 1 \leq H \leq 10^4
  • 1 \leq W \leq 50
  • H, W は整数である。
  • a_{i,j}.# のいずれかである。

入力

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

H W
a_{1,1} ... a_{1,W}
:
a_{H,1} ... a_{H,W}

出力

赤マスに塗り替える白マスの数の最小値とそのときの塗り方の個数を 10^9 + 7 で割った余りを空白区切りで一行に出力せよ。 条件を満たす塗り方が存在しない場合は -1 のみを出力せよ。


入力例1

2 3
...
.#.

出力例1

4 4

赤マスに塗られたマスを o で表したとき、塗り方は以下の 4 通りです。

ooo  ooo  oo.  .oo
o#.  .#o  o#o  o#o

入力例2

2 3
#..
.##

出力例2

-1

条件を満たす塗り方は存在しません。


入力例3

3 10
...#...#..
#...#...#.
..##......

出力例3

12 35640

入力例4

6 6
......
......
......
......
......
......

出力例4

11 60466176

Score : 400 points

Problem Statement

There is a grid with H rows and W columns. Originally, each cell in the grid is painted white or black. The cell on the i-th row and j-th column is painted white if a_{i,j} is .. It is painted black if a_{i,j} is #. You want to paint some white cells red within the following constraints.

  • Each row and column must have one or more red cells.
  • When a graph is constructed as follows, the graph must be connected.
    • For all red cells, create the corresponding vertices. (The number of vertices in the graph is equal to the number of red cells in the grid. )
    • Add edges to all pairs of vertices, the corresponding cells of which are on the same row or column.

Find the minimum number of cells you need to paint red to sarisfy the above constraints. Also, find the number of such ways (where the number of red cells is minimum) module 10^9 + 7.

Constraints

  • 1 \leq H \leq 10^4
  • 1 \leq W \leq 50
  • H, W are integers.
  • a_{i,j} is either . or #.

Input

Input is given from Standard Input in the following format:

H W
a_{1,1} ... a_{1,W}
:
a_{H,1} ... a_{H,W}

Output

Print the minimum number of cells you need to paint red and the number of such ways, with a single space in between. If there's no ways to satisfy the constraints, print only -1 instead.


Sample Input 1

2 3
...
.#.

Sample Output 1

4 4

There are 4 ways to paint the grid. (o represents a red cell. )

ooo  ooo  oo.  .oo
o#.  .#o  o#o  o#o

Sample Input 2

2 3
#..
.##

Sample Output 2

-1

There are no ways to satisfy the constraints.


Sample Input 3

3 10
...#...#..
#...#...#.
..##......

Sample Output 3

12 35640

Sample Input 4

6 6
......
......
......
......
......
......

Sample Output 4

11 60466176

Source Name

KUPC2017
K - Xor Summation Pattern

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400

問題文

整数 n, m, k が入力として与えられます。このとき、以下の条件を満たす長さ n の数列 s の個数を 10^9 + 7 で割った余りを求めてください。

  1. s_i (1 \leq i \leq n)0 以上 m 以下の整数である。
  2. 0\ xor\ s_1\ xor\ s_2\ xor\ ...\ s_n = k である。ただし、xor はビットごとの排他的論理和を表すものとする。

制約

  • n, m, k は整数である。
  • 0 \leq n, m, k \leq 10^{18}

入力

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

n m k

出力

問題文の条件を満たす数列 s の個数を 10^9 + 7 で割った余りを出力せよ。


入力例1

0 0 0

出力例1

1

長さが 0 の数列は 1 通りです。このときこの数列は条件 2 も満たします。


入力例2

1 1 0

出力例2

1

入力例3

3 2 3

出力例3

6

以下の 6 通りの数列が存在します。

  • { 0, 1, 2 }
  • { 0, 2, 1 }
  • { 1, 0, 2 }
  • { 1, 2, 0 }
  • { 2, 0, 1 }
  • { 2, 1, 0 }

入力例4

10 10 15

出力例4

620478679

Score : 400 points

Problem Statement

You have 3 integers n, m, and k. Count the number of numerical sequences of length n, which satisfy the following conditions, modulo 10^9 + 7.

  1. s_i (1 \leq i \leq n) is an integer greather than or equal to 0, and less than or equal to m.
  2. 0\ xor\ s_1\ xor\ s_2\ xor\ ...\ s_n = k. xor represents bitwise exclusive OR.

Constraints

  • n, m, k are integers.
  • 0 \leq n, m, k \leq 10^{18}

Input

Input is given from Standard Input in the following format:

n m k

Output

Print the number of numerical sequences that satisfy the above conditions, modulo 10^9 + 7.


Sample Input 1

0 0 0

Sample Output 1

1

The number of numerical sequences with length 1 is 1. This sequence satisfies condition 2.


Sample Input 2

1 1 0

Sample Output 2

1

Sample Input 3

3 2 3

Sample Output 3

6

The following 6 sequences satisfy the constraints.

  • { 0, 1, 2 }
  • { 0, 2, 1 }
  • { 1, 0, 2 }
  • { 1, 2, 0 }
  • { 2, 0, 1 }
  • { 2, 1, 0 }

Sample Input 4

10 10 15

Sample Output 4

620478679

Source Name

KUPC2017
L - Coin Game 2017

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400

問題文

HW 列に区切られた盤面があり、盤面の各マスは「表向きのコインが 1 枚置かれている」「裏向きのコインが 1 枚置かれている」「コインが置かれていない」のいずれかです。

また、「1 行目」「2 行目」...「H 行目」「1 列目」「2 列目」...「W 列目」と書かれたカードが 1 枚ずつ合計 W + H 枚あります。

この盤面とこれらのカードを使い、2 人でゲームを行います。

ゲームは、ゲームが終了するまで手番を交互に繰り返します。 各手番は以下の手順で行います。

  1. 手番プレイヤーはカードを 1 枚自由に選んで取り除く
  2. 取り除いたカードに書かれた行または列にある全てのコインの裏表を反転させる
  3. 取り除くカードがなくなった場合、もしくは盤面上の全てのコインが表向きになった場合、ゲームは終了する

ゲーム終了後、各プレイヤーはゲーム終了時の状態に応じて以下の点数を得ます。

  • 最後にカードを取り除いたプレイヤーは 1 点を得る
  • 盤面上の全てのコインが表向きになっていれば、お互いに 2 点を追加で得る

お互いに自分の得る合計点数を最大化するように最適に行動したとき、先手が得る合計点数を求めてください。

制約

  • 1 \leq W, H \leq 2,000
  • m_{ij}., o, x のいずれかである
  • 裏向きのコインが少なくとも 1 枚置かれている

部分点

以下の追加制約を満たすデータセットに正解した場合は、30 点が与えられる。

  • 各行には裏向きのコインが少なくとも 1 枚置かれている
  • 各列には表向きまたは裏向きのコインが少なくとも 1 枚置かれている

追加制約のないデータセットに正解した場合は、上記とは別に 370 点が与えられる。


入力

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

m_{ij}ij 列の状態を表しており、 . の場合コインが置かれていないことを、 o の場合表向きのコインが置かれていることを、 x の場合裏向きのコインが置かれていることを表す。

H W
m_{11} m_{12} ... m_{1W}
m_{21} m_{22} ... m_{2W}
:
m_{H1} m_{H2} ... m_{HW}

出力

お互いに自分の得る合計点数を最大化するように最適に行動したとき、先手が得る合計点数を 1 行で出力せよ。


入力例1

2 5
.x.x.
x.o.x

出力例1

3

この入力例は追加制約を満たします。


入力例2

7 2
x.
xx
x.
xx
x.
xx
x.

出力例2

3

この入力例は追加制約を満たします。


入力例3

4 3
x.o
.x.
x.x
...

出力例3

1

入力例4

5 1
x
o
.
o
x

出力例4

2

入力例5

39 40
.........o..............................
.............................o..........
.................o......................
......o...............................x.
...x......o.............................
...........................o......o.....
.........................x..............
.................o.............o........
..................x.....................
.............o..........................
.......................................o
...............o........................
.....x.....o............................
..................o.....................
..o.........o...........................
...............x........................
.......o............................x...
........................x.....o.........
...................o.........o..........
........x..........................o....
......................o...o.............
..............o..................o......
..............x.........................
x.......................................
..o....................x................
.........................o..............
.o...................................o..
.................................o......
.o..................x...................
...........o....o.......................
.............x..........................
...............................x........
....o..............................o....
..........................o.x...........
...................x....................
.....................................o..
.........x..............................
o......................................o
.....................x..........o.......

出力例5

3

入力例6

38 39
.......o............................x..
.........x.............................
................x......................
............x..........................
.................x..........o..........
..................................o..o.
...............................o.......
.....................x..........o......
.............o.........................
..o....................o...............
....x..................................
...................o...................
..................o....................
.....x.....o...........................
.o..................o..................
....................o......x...........
.........................o.............
..................x....................
...............o.......................
......o...............................x
.......................o.........x.....
...............x.......................
.o.....................................
.........o.............................
o......................................
..............o.......o................
............o......o...................
........o..........................o...
..........................o.o..........
...x......o............................
......................x................
.............x.........................
o...o..................................
........o....................x.........
..............o........................
................o..............o.......
........................x.....o........
.........................x.............

出力例6

2

Score : 400 points

Problem Statement

There are a board with H rows and W columns. Each cell on the board is one of the following states: "one coin is placed face up", "one coin is placed face down", or "no coin is placed".

There are also W + H cards and one of the following is written on each card: "Row 1", "Row 2", ..., "Row H", "Column 1", "Column 2", ..., and "Column W". (Each type is written on exactly one card.)

Two players play a game using the board and cards. In this game, two players play their turns alternatingly.

In each turn, one of the players takes the following actions.

  • The player removes 1 card he or she wants to.
  • When a card is removed, all the coins on the row or column written on the card are turned over.
  • The game ends when they have removed all cards or when all the coins are facing up.

When the game ends, the players earn scores according to the final state of the game as follows.

  • The player who remove a card last earns 1 point.
  • If all the coins are facing up, both players earn 2 points.

Find the total score of the first mover, assuming that both players play optimally to maximize their own scores.

Constraints

  • 1 \leq W, H \leq 2,000
  • m_{ij} is ., o, or x
  • One or more coins are facing down

Partial Scores

30 points will be awarded for passing the test set satisfying the following:

  • There are at least one coins facing down on each row.
  • There are at least one coins facing up or down on each column.

Another 370 points will be awarded for passing the test set without addtional constraints and you can get 400 points in total.


Input

Input is given from Standard Input in the following format:

m_{ij} represents the state on row i and column j, ., o, and x indicate "no coin is placed", "a coin is placed face up", and "a coin is placed face down", respectively.

H W
m_{11} m_{12} ... m_{1W}
m_{21} m_{22} ... m_{2W}
:
m_{H1} m_{H2} ... m_{HW}

Output

Print the total score of the first mover, assuming that both players play optimally to maximize their own scores.


Sample Input 1

2 5
.x.x.
x.o.x

Sample Output 1

3

This input satisfies the additional constraint.


Sample Input 2

7 2
x.
xx
x.
xx
x.
xx
x.

Sample Output 2

3

This input satisfies the additional constraint.


Sample Input 3

4 3
x.o
.x.
x.x
...

Sample Output 3

1

Sample Input 4

5 1
x
o
.
o
x

Sample Output 4

2

Sample Input 5

39 40
.........o..............................
.............................o..........
.................o......................
......o...............................x.
...x......o.............................
...........................o......o.....
.........................x..............
.................o.............o........
..................x.....................
.............o..........................
.......................................o
...............o........................
.....x.....o............................
..................o.....................
..o.........o...........................
...............x........................
.......o............................x...
........................x.....o.........
...................o.........o..........
........x..........................o....
......................o...o.............
..............o..................o......
..............x.........................
x.......................................
..o....................x................
.........................o..............
.o...................................o..
.................................o......
.o..................x...................
...........o....o.......................
.............x..........................
...............................x........
....o..............................o....
..........................o.x...........
...................x....................
.....................................o..
.........x..............................
o......................................o
.....................x..........o.......

Sample Output 5

3

Sample Input 6

38 39
.......o............................x..
.........x.............................
................x......................
............x..........................
.................x..........o..........
..................................o..o.
...............................o.......
.....................x..........o......
.............o.........................
..o....................o...............
....x..................................
...................o...................
..................o....................
.....x.....o...........................
.o..................o..................
....................o......x...........
.........................o.............
..................x....................
...............o.......................
......o...............................x
.......................o.........x.....
...............x.......................
.o.....................................
.........o.............................
o......................................
..............o.......o................
............o......o...................
........o..........................o...
..........................o.o..........
...x......o............................
......................x................
.............x.........................
o...o..................................
........o....................x.........
..............o........................
................o..............o.......
........................x.....o........
.........................x.............

Sample Output 6

2

Source Name

KUPC2017