A - To Be Saikyo

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 から N までの番号が付けられた N 人の人がいます。 それぞれの人にはプログラミング力という整数値が定まっており、人 i のプログラミング力は P_i です。 人 1 が最強になるためには、あといくつプログラミング力を上げる必要がありますか? すなわち、すべての i \neq 1 に対して P_1 + x > P_i を満たすような最小の非負整数 x は何ですか?

制約

  • 1\leq N \leq 100
  • 1\leq P_i \leq 100
  • 入力は全て整数

入力

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

N
P_1 P_2 \dots P_N

出力

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


入力例 1

4
5 15 2 10

出力例 1

11

人 1 が最強になるためには、プログラミング力を 16 以上にする必要があります。 よって、答えは 16-5=11 です。


入力例 2

4
15 5 2 10

出力例 2

0

人 1 は既に最強なので、これ以上プログラミング力を上げる必要はありません。


入力例 3

3
100 100 100

出力例 3

1

Score : 100 points

Problem Statement

There are N people numbered 1 through N. Each person has a integer score called programming ability; person i's programming ability is P_i points. How many more points does person 1 need, so that person 1 becomes the strongest? In other words, what is the minimum non-negative integer x such that P_1 + x > P_i for all i \neq 1?

Constraints

  • 1\leq N \leq 100
  • 1\leq P_i \leq 100
  • All input values are integers.

Input

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

N
P_1 P_2 \dots P_N

Output

Print the answer as an integer.


Sample Input 1

4
5 15 2 10

Sample Output 1

11

Person 1 becomes the strongest when their programming skill is 16 points or more, so the answer is 16-5=11.


Sample Input 2

4
15 5 2 10

Sample Output 2

0

Person 1 is already the strongest, so no more programming skill is needed.


Sample Input 3

3
100 100 100

Sample Output 3

1
B - Saturday

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

ある日、学校へ行くのに疲れてしまった高橋くんは、土曜日まであと何日あるかを知りたくなりました。
その日は平日で、曜日を英語で表すと S だったことが分かっています。その日より後の直近の土曜日は何日後かを求めてください。

なお、月曜日、火曜日、水曜日、木曜日、金曜日はそれぞれ英語で Monday, Tuesday, Wednesday, Thursday, Friday です。

制約

  • S は Monday, Tuesday, Wednesday, Thursday, Friday のいずれかである

入力

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

S

出力

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


入力例 1

Wednesday

出力例 1

3

この日は水曜日なので、3 日後に土曜日になります。


入力例 2

Monday

出力例 2

5

Score : 100 points

Problem Statement

One day, tired from going to school, Takahashi wanted to know how many days there were until Saturday.
We know that the day was a weekday, and the name of the day of the week was S in English.
How many days were there until the first Saturday after that day (including Saturday but not the starting day)?

Constraints

  • S is Monday, Tuesday, Wednesday, Thursday, or Friday.

Input

Input is given from Standard Input in the following format:

S

Output

Print the answer as an integer.


Sample Input 1

Wednesday

Sample Output 1

3

It was Wednesday, so there were 3 days until the first Saturday after that day.


Sample Input 2

Monday

Sample Output 2

5
C - ABCDEFG

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

直線上に 7 個の点 A, B, C, D, E, F, G がこの順に並んでいます。(下の図も参考にしてください)
隣り合う点の距離は次の通りです。

  • 点 A と点 B の距離は 3
  • 点 B と点 C の距離は 1
  • 点 C と点 D の距離は 4
  • 点 D と点 E の距離は 1
  • 点 E と点 F の距離は 5
  • 点 F と点 G の距離は 9

image

2 つの英大文字 p, q が与えられます。p, q は A,B,C,D,E,F,G のいずれかで、 p \neq q が成り立ちます。
点 p と点 q の間の距離を答えてください。

制約

  • p, q は A,B,C,D,E,F,G のいずれか
  • p \neq q

入力

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

p q

出力

点 p と点 q の間の距離を出力せよ。


入力例 1

A C

出力例 1

4

点 A と点 C の距離は 3 + 1 = 4 です。


入力例 2

G B

出力例 2

20

点 G と点 B の距離は 9 + 5 + 1 + 4 + 1 = 20 です。


入力例 3

C F

出力例 3

10

Score : 200 points

Problem Statement

There are 7 points A, B, C, D, E, F, and G on a straight line, in this order. (See also the figure below.)
The distances between adjacent points are as follows.

  • Between A and B: 3
  • Between B and C: 1
  • Between C and D: 4
  • Between D and E: 1
  • Between E and F: 5
  • Between F and G: 9

image

You are given two uppercase English letters p and q. Each of p and q is A, B, C, D, E, F, or G, and it holds that p \neq q.
Find the distance between the points p and q.

Constraints

  • Each of p and q is A,B,C,D,E,F, or G.
  • p \neq q

Input

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

p q

Output

Print the distance between the points p and q.


Sample Input 1

A C

Sample Output 1

4

The distance between the points A and C is 3 + 1 = 4.


Sample Input 2

G B

Sample Output 2

20

The distance between the points G and B is 9 + 5 + 1 + 4 + 1 = 20.


Sample Input 3

C F

Sample Output 3

10
D - Get Closer

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

二次元平面上の点 (0,0) から点 (A,B) に向かって距離 1 だけ移動します。移動後の座標を求めてください。

ただし、点 X から点 Y に向かって距離 d (\le 線分 XY の長さ) だけ移動すると、線分 XY 上で点 X からの距離が d であるような点に辿りつくものとします。
なお、制約より点 (0,0) と点 (A,B) の距離は 1 以上であることが保証されます。

制約

  • 入力は全て整数
  • 0 \le A,B \le 1000
  • (A,B) \neq (0,0)

入力

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

A B

出力

移動後の点を (x,y) とするとき、 x と y をこの順に空白区切りで出力せよ。
なお、各出力について、想定解との絶対誤差または相対誤差が 10^{−6} 以下であれば正解として扱われる。


入力例 1

3 4

出力例 1

0.600000000000 0.800000000000

他にも、例えば 0.5999999999 0.8000000001 という出力も許容されます。


入力例 2

1 0

出力例 2

1.000000000000 0.000000000000

点 (A,B) に到着する場合もあります。


入力例 3

246 402

出力例 3

0.521964870245 0.852966983083

Score : 200 points

Problem Statement

From the point (0,0) in a two-dimensional plane, let us move the distance of 1 toward the point (A, B). Find our coordinates after the move.

Here, after moving the distance of d from a point X to a point Y (d \le length of the segment XY), we are at the point on the segment XY whose distance from X is d.
The Constraints guarantee that the distance between the points (0, 0) and (A, B) is at least 1.

Constraints

  • All values in input are integers.
  • 0 \le A,B \le 1000
  • (A,B) \neq (0,0)

Input

Input is given from Standard Input in the following format:

A B

Output

Let (x, y) be our coordinates after the move. Print x and y in this order, separated by a space.
Your output is considered correct when, for each printed value, the absolute or relative error from the judge's answer is at most 10^{−6}.


Sample Input 1

3 4

Sample Output 1

0.600000000000 0.800000000000

Printing 0.5999999999 0.8000000001, for example, would also be accepted.


Sample Input 2

1 0

Sample Output 2

1.000000000000 0.000000000000

We may arrive at (A, B).


Sample Input 3

246 402

Sample Output 3

0.521964870245 0.852966983083
E - One More aab aba baa

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

文字列 S の各文字を並べ替えて作ることが可能な文字列を辞書順にすべて列挙したとき、前から K 番目にくる文字列を求めてください。

「各文字を並べ替えて作ることが可能な文字列」とは? 「文字列 A が文字列 B の各文字を並べ替えて作ることが可能な文字列である」とは、任意の文字が文字列 A と文字列 B に同数含まれるということを指します。

制約

  • 1 \le |S| \le 8
  • S は英小文字のみからなる
  • S の各文字を並べ替えてできる文字列は K 種類以上存在する

入力

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

S K

出力

答えを出力せよ。


入力例 1

aab 2

出力例 1

aba

文字列 aab の各文字を並べ替えて作ることが可能な文字列は \{ aab, aba, baa \} の 3 つですが、このうち辞書順で前から 2 番目にくるものは aba です。


入力例 2

baba 4

出力例 2

baab

入力例 3

ydxwacbz 40320

出力例 3

zyxwdcba

Score : 300 points

Problem Statement

Find the K-th lexicographically smallest string among the strings that are permutations of a string S.

What is a permutation of a string?A string A is said to be a permutation of a string B when any character occurs the same number of times in A and B.

Constraints

  • 1 \le |S| \le 8
  • S consists of lowercase English letters.
  • There are at least K distinct strings that are permutations of S.

Input

Input is given from Standard Input in the following format:

S K

Output

Print the answer.


Sample Input 1

aab 2

Sample Output 1

aba

There are three permutations of a string aab: \{ aab, aba, baa \}. The 2-nd lexicographically smallest of them is aba.


Sample Input 2

baba 4

Sample Output 2

baab

Sample Input 3

ydxwacbz 40320

Sample Output 3

zyxwdcba
F - Dango

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

正の整数 L に対して、 レベル L のダンゴ文字列とは、以下の条件を満たす文字列です。

  • o と - からなる長さ L+1 の文字列である。
  • 先頭の文字と末尾の文字のうちちょうど一方が - であり、そのほかの L 文字はすべて o である。

例えば、ooo- はレベル 3 のダンゴ文字列ですが、-ooo- や oo や o-oo- などはダンゴ文字列ではありません(より正確には、どのような正の整数 L に対してもレベル L のダンゴ文字列ではありません)。

2 種類の文字 o - からなる、長さ N の文字列 S が与えられます。 次の条件を満たすような正整数 X のうち、最大のものを求めてください。

  • S の連続する部分文字列であって、レベル X のダンゴ文字列であるものが存在する。

ただし、そのような整数が存在しない場合、-1 と出力してください。

制約

  • 1\leq N\leq 2\times10^5
  • S は o - からなる長さ N の文字列

入力

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

N
S

出力

S にレベル X のダンゴ文字列が含まれるような最大の X の値を 1 行で出力せよ。 そのような値が存在しない場合、-1 を出力せよ。


入力例 1

10
o-oooo---o

出力例 1

4

たとえば、S の 3 文字目から 7 文字目までに対応する部分文字列 oooo- は、レベル 4 のダンゴ文字列です。 S の部分文字列であってレベル 5 以上のダンゴ文字列であるようなものは存在しないため、4 と出力してください。


入力例 2

1
-

出力例 2

-1

S の連続する部分文字列は空文字列と - の 2 種類だけです。 これらはダンゴ文字列ではないため、-1 と出力してください。


入力例 3

30
-o-o-oooo-oo-o-ooooooo--oooo-o

出力例 3

7

Score : 300 points

Problem Statement

For a positive integer L, a level-L dango string is a string that satisfies the following conditions.

  • It is a string of length L+1 consisting of o and -.
  • Exactly one of the first character and the last character is -, and the other L characters are o.

For instance, ooo- is a level-3 dango string, but none of -ooo-, oo, and o-oo- is a dango string (more precisely, none of them is a level-L dango string for any positive integer L).

You are given a string S of length N consisting of the two characters o and -. Find the greatest positive integer X that satisfies the following condition.

  • There is a contiguous substring of S that is a level-X dango string.

If there is no such integer, print -1.

Constraints

  • 1\leq N\leq 2\times10^5
  • S is a string of length N consisting of o and -.

Input

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

N
S

Output

Print the greatest positive integer X such that S contains a level-X dango string, or -1 if there is no such integer.


Sample Input 1

10
o-oooo---o

Sample Output 1

4

For instance, the substring oooo- corresponding to the 3-rd through 7-th characters of S is a level-4 dango string. No substring of S is a level-5 dango string or above, so you should print 4.


Sample Input 2

1
-

Sample Output 2

-1

Only the empty string and - are the substrings of S. They are not dango strings, so you should print -1.


Sample Input 3

30
-o-o-oooo-oo-o-ooooooo--oooo-o

Sample Output 3

7
G - Peaceful Teams

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 人のスポーツ選手がいます。

N 人の選手たちには互いに相性の悪い選手のペアが M 組あり、相性の悪い組のうち i\ (1\leq i\leq M) 組目は A _ i 番目の選手と B _ i 番目の選手です。

あなたは、選手を T チームに分けます。 どの選手もちょうど一つのチームに属さなければならず、どのチームにも少なくとも一人の選手が属さなければなりません。 さらに、どの i=1,2,\ldots,M についても、 A _ i 番目の選手と B _ i 番目の選手が同じチームに属していてはいけません。

この条件を満たすチーム分けの方法は何通りあるか求めてください。 ただし、チーム分けの方法が異なるとは、ある二人が存在して、彼らが一方のチーム分けでは同じチームに所属し、もう一方では異なるチームに所属することをいいます。

制約

  • 1\leq T\leq N\leq10
  • 0\leq M\leq\dfrac{N(N-1)}2
  • 1\leq A _ i\lt B _ i\leq N\ (1\leq i\leq M)
  • (A _ i,B _ i)\neq (A _ j,B _ j)\ (1\leq i\lt j\leq M)
  • 入力はすべて整数

入力

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

N T M
A _ 1 B _ 1
A _ 2 B _ 2
\vdots
A _ M B _ M

出力

答えを 1 行で出力せよ。


入力例 1

5 2 2
1 3
3 4

出力例 1

4

次の 4 通りのチーム分けが条件を満たします。

他に条件を満たすチーム分けは存在しないので、4 を出力してください。


入力例 2

5 1 2
1 3
3 4

出力例 2

0

条件を満たすチーム分けがひとつも存在しないこともあります。


入力例 3

6 4 0

出力例 3

65

相性の悪いペアがひとつも存在しないこともあります。


入力例 4

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

出力例 4

8001

Score : 400 points

Problem Statement

There are N sports players.

Among them, there are M incompatible pairs. The i-th incompatible pair (1\leq i\leq M) is the A_i-th and B_i-th players.

You will divide the players into T teams. Every player must belong to exactly one team, and every team must have one or more players. Additionally, for each i=1,2,\ldots,M, the A_i-th and B_i-th players must not belong to the same team.

Find the number of ways to satisfy these conditions. Here, two divisions are considered different when there are two players who belong to the same team in one division and different teams in the other.

Constraints

  • 1\leq T\leq N\leq10
  • 0\leq M\leq\dfrac{N(N-1)}2
  • 1\leq A _ i\lt B _ i\leq N\ (1\leq i\leq M)
  • (A _ i,B _ i)\neq (A _ j,B _ j)\ (1\leq i\lt j\leq M)
  • All input values are integers.

Input

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

N T M
A _ 1 B _ 1
A _ 2 B _ 2
\vdots
A _ M B _ M

Output

Print the answer in a single line.


Sample Input 1

5 2 2
1 3
3 4

Sample Output 1

4

The following four divisions satisfy the conditions.

No other division satisfies them, so print 4.


Sample Input 2

5 1 2
1 3
3 4

Sample Output 2

0

There may be no division that satisfies the conditions.


Sample Input 3

6 4 0

Sample Output 3

65

There may be no incompatible pair.


Sample Input 4

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

Sample Output 4

8001
H - Takahashi's Anguish

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

1 から N の番号がついた N 人の人がいます。
高橋君は 1 から N までの整数を並び替えた列 P = (P_1, P_2, \dots, P_N) を 1 つ選んで、 人 P_1, 人 P_2, \dots, 人 P_N の順番に 1 人ずつキャンディを配ることにしました。
人 i は人 X_i のことが嫌いなので、高橋君が人 i より先に人 X_i にキャンディを配った場合、人 i に不満度 C_i がたまります。そうでない場合の人 i の不満度は 0 です。
高橋君が P を自由に選べるとき、全員の不満度の和の最小値はいくつになりますか?

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq X_i \leq N
  • X_i \neq i
  • 1 \leq C_i \leq 10^9
  • 入力される値はすべて整数

入力

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

N
X_1 X_2 \dots X_N
C_1 C_2 \dots C_N

出力

答えを出力せよ。


入力例 1

3
2 3 2
1 10 100

出力例 1

10

P = (1, 3, 2) とすれば不満度が正になるのは人 2 だけで、この時全員の不満度の和は 10 になります。
これより不満度の和を小さくすることはできないので、答えは 10 です。


入力例 2

8
7 3 5 5 8 4 1 2
36 49 73 38 30 85 27 45

出力例 2

57

Score : 500 points

Problem Statement

There are N people numbered 1 through N.
Takahashi has decided to choose a sequence P = (P_1, P_2, \dots, P_N) that is a permutation of integers from 1 through N, and give a candy to Person P_1, Person P_2, \dots, and Person P_N, in this order.
Since Person i dislikes Person X_i, if Takahashi gives a candy to Person X_i prior to Person i, then Person i gains frustration of C_i; otherwise, Person i's frustration is 0.
Takahashi may arbitrarily choose P. What is the minimum possible sum of their frustration?

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq X_i \leq N
  • X_i \neq i
  • 1 \leq C_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
X_1 X_2 \dots X_N
C_1 C_2 \dots C_N

Output

Print the answer.


Sample Input 1

3
2 3 2
1 10 100

Sample Output 1

10

If he lets P = (1, 3, 2), only Person 2 gains a positive amount of frustration, in which case the sum of their frustration is 10.
Since it is impossible to make the sum of frustration smaller, the answer is 10.


Sample Input 2

8
7 3 5 5 8 4 1 2
36 49 73 38 30 85 27 45

Sample Output 2

57
I - No Passage

Time Limit: 2.5 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

H 行 W 列のグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表します。また、このうち K 個のマスはゴールになっています。i 個目 (1 \leq i \leq K) のゴールはマス (R_i, C_i) です。

高橋君と青木君はこのグリッドとグリッドの上に置かれた 1 つのコマを使ってあるゲームをしています。高橋君と青木君はコマがゴールのマスに到達するまで以下の一連の操作を繰り返し行います。

  • 青木君は 1 以上 4 以下の整数 a を選ぶ。
  • その後、高橋君は 1 以上 4 以下の整数 b を選ぶ。ただし、a \neq b を満たす必要がある。操作前にコマが置いてあるマスを (i,j) としたとき、選んだ整数 b とコマの位置に応じて以下の通りにコマを移動させる。
    • b=1 のとき: マス (i-1,j) がグリッド内である場合はコマをマス (i,j) からマス (i-1,j) に移動させ、グリッドの外である場合はコマを移動させない。
    • b=2 のとき: マス (i+1,j) がグリッド内である場合はコマをマス (i,j) からマス (i+1,j) に移動させ、グリッドの外である場合はコマを移動させない。
    • b=3 のとき: マス (i,j-1) がグリッド内である場合はコマをマス (i,j) からマス (i,j-1) に移動させ、グリッドの外である場合はコマを移動させない。
    • b=4 のとき: マス (i,j+1) がグリッド内である場合はコマをマス (i,j) からマス (i,j+1) に移動させ、グリッドの外である場合はコマを移動させない。

高橋君の目的はコマがゴールに到達するまでの移動回数を最小化することです。青木君の目的はコマがゴールに到達しないようにすることであり、それが不可能な場合は移動回数を最大化することです。

1 \leq i \leq H,1 \leq j \leq W を満たすすべての整数の組 (i,j) に対して以下の問題を解き、解の総和を求めてください。

コマがマス (i,j) にある状態からゲームを始める。両者が各々の目的を目指して最適に行動するとき、高橋君がコマをゴールに到達させることができるのであれば移動回数の最小値、そうでないならば 0 が解である。

制約

  • 2 \leq H \leq 3000
  • 2 \leq W \leq 3000
  • 1 \leq K \leq \min(HW,3000)
  • 1 \leq R_i \leq H
  • 1 \leq C_i \leq W
  • (R_i,C_i) \neq (R_j,C_j) (1 \leq i < j \leq K)
  • 入力はすべて整数

入力

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

H W K
R_1 C_1
R_2 C_2
\vdots
R_K C_K

出力

答えを出力せよ。


入力例 1

2 3 2
1 2
2 1

出力例 1

2

(i,j)=(1,2),(2,1) のとき、開始するマスがゴールであるため、解は 0 です。

(i,j)=(1,1),(2,2) のとき、どの a を青木君が選んでも高橋君は 1 回の移動でコマをゴールに到達させることができるため、解は 1 です。

(i,j)=(1,3),(2,3) のとき、高橋君はコマをゴールに到達させることができないため、解は 0 です。

これらの合計は 0 \times 2 + 1 \times 2 + 0 \times 2 = 2 です。よって 2 を出力します。


入力例 2

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

出力例 2

43

入力例 3

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

出力例 3

153

Score : 525 points

Problem Statement

There is an H \times W grid. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. Among these, K cells are goals. The i-th goal (1 \leq i \leq K) is cell (R_i, C_i).

Takahashi and Aoki play a game using this grid and a single piece placed on the grid. Takahashi and Aoki repeatedly perform the following series of operations until the piece reaches a goal cell:

  • Aoki chooses an integer a between 1 and 4, inclusive.
  • Then, Takahashi chooses an integer b between 1 and 4, inclusive, where a \neq b must be satisfied. Let (i,j) be the cell where the piece is placed before the operation. Based on the chosen integer b and the piece's position, move the piece.
    • When b=1: If (i-1,j) is within the grid, move the piece from cell (i,j) to cell (i-1,j); if it is outside the grid, do nothing.
    • When b=2: If (i+1,j) is within the grid, move the piece from cell (i,j) to cell (i+1,j); if it is outside the grid, do nothing.
    • When b=3: If (i,j-1) is within the grid, move the piece from cell (i,j) to cell (i,j-1); if it is outside the grid, do nothing.
    • When b=4: If (i,j+1) is within the grid, move the piece from cell (i,j) to cell (i,j+1); if it is outside the grid, do nothing.

Takahashi's objective is to minimize the number of moves until the piece reaches a goal. Aoki's objective is to prevent the piece from reaching the goal; if that is impossible, his objective is to maximize the number of moves until the piece reaches a goal.

For all pairs of integers (i,j) satisfying 1 \leq i \leq H,1 \leq j \leq W, solve the following problem and find the sum of all solutions:

Start the game with the piece at cell (i,j). Assume both players act optimally toward their respective objectives. If Takahashi can make the piece reach a goal, the solution is the minimum number of moves; otherwise, the solution is 0.

Constraints

  • 2 \leq H \leq 3000
  • 2 \leq W \leq 3000
  • 1 \leq K \leq \min(HW,3000)
  • 1 \leq R_i \leq H
  • 1 \leq C_i \leq W
  • (R_i,C_i) \neq (R_j,C_j) (1 \leq i < j \leq K)
  • All input values are integers.

Input

The input is given from standard input in the following format:

H W K
R_1 C_1
R_2 C_2
\vdots
R_K C_K

Output

Print the answer.


Sample Input 1

2 3 2
1 2
2 1

Sample Output 1

2

When (i,j)=(1,2),(2,1), the starting cell is a goal, so the solution is 0.

When (i,j)=(1,1),(2,2), no matter which a Aoki chooses, Takahashi can make the piece reach a goal in 1 move from the starting cell, so the solution is 1.

When (i,j)=(1,3),(2,3), Takahashi cannot reach a goal, so the solution is 0.

The sum of these is 0 \times 2 + 1 \times 2 + 0 \times 2 = 2. Thus, print 2.


Sample Input 2

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

Sample Output 2

43

Sample Input 3

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

Sample Output 3

153