Problem Statement

It has been decided that a programming contest sponsored by company A will be held, so we will post the notice on a bulletin board.

The bulletin board is in the form of a grid with N rows and N columns, and the notice will occupy a rectangular region with H rows and W columns.

How many ways are there to choose where to put the notice so that it completely covers exactly HW squares?

Constraints

• 1 \leq H, W \leq N \leq 100
• All values in input are integers.

Sample Input 1

3
2
3

Sample Output 1

2

There are two ways to put the notice, as follows:

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

Here, # represents a square covered by the notice, and . represents a square not covered.

Sample Input 2

100
1
1

Sample Output 2

10000

Sample Input 3

5
4
2

Sample Output 3

8

Problem Statement

You have written N problems to hold programming contests. The i-th problem will have a score of P_i points if used in a contest.

With these problems, you would like to hold as many contests as possible under the following condition:

• A contest has three problems. The first problem has a score not greater than A points, the second has a score between A + 1 and B points (inclusive), and the third has a score not less than B + 1 points.

The same problem should not be used in multiple contests. At most how many contests can be held?

Constraints

• 3 \leq N \leq 100
• 1 \leq P_i \leq 20 (1 \leq i \leq N)
• 1 \leq A < B < 20
• All values in input are integers.

Sample Input 1

7
5 15
1 10 16 2 7 20 12

Sample Output 1

2

Two contests can be held by putting the first, second, third problems and the fourth, fifth, sixth problems together.

Sample Input 2

8
3 8
5 5 5 10 10 10 15 20

Sample Output 2

0

No contest can be held, because there is no problem with a score of A = 3 or less.

Sample Input 3

3
5 6
5 6 10

Sample Output 3

1

Problem Statement

There is a grid with H rows and W columns, where each square is painted black or white.

You are given H strings S_1, S_2, ..., S_H, each of length W. If the square at the i-th row from the top and the j-th column from the left is painted black, the j-th character in the string S_i is #; if that square is painted white, the j-th character in the string S_i is ..

Find the number of pairs of a black square c_1 and a white square c_2 that satisfy the following condition:

• There is a path from the square c_1 to the square c_2 where we repeatedly move to a vertically or horizontally adjacent square through an alternating sequence of black and white squares: black, white, black, white...

Constraints

• 1 \leq H, W \leq 400
• |S_i| = W (1 \leq i \leq H)
• For each i (1 \leq i \leq H), the string S_i consists of characters # and ..

Sample Input 1

3 3
.#.
..#
#..

Sample Output 1

10

Some of the pairs satisfying the condition are ((1, 2), (3, 3)) and ((3, 1), (3, 2)), where (i, j) denotes the square at the i-th row from the top and the j-th column from the left.

Sample Input 2

2 4
....
....

Sample Output 2

0

Sample Input 3

4 3
###
###
...
###

Sample Output 3

6

Problem Statement

There are N cards. The i-th card has an integer A_i written on it. For any two cards, the integers on those cards are different.

Using these cards, Takahashi and Aoki will play the following game:

• Aoki chooses an integer x.
• Starting from Takahashi, the two players alternately take a card. The card should be chosen in the following manner:
  • Takahashi should take the card with the largest integer among the remaining card.
  • Aoki should take the card with the integer closest to x among the remaining card. If there are multiple such cards, he should take the card with the smallest integer among those cards.
• The game ends when there is no card remaining.

You are given Q candidates for the value of x: X_1, X_2, ..., X_Q. For each i (1 \leq i \leq Q), find the sum of the integers written on the cards that Takahashi will take if Aoki chooses x = X_i.

Constraints

• 2 \leq N \leq 100 000
• 1 \leq Q \leq 100 000
• 1 \leq A_1 < A_2 < ... < A_N \leq 10^9
• 1 \leq X_i \leq 10^9 (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

5 5
3 5 7 11 13
1
4
9
10
13

Sample Output 1

31
31
27
23
23

For example, when x = X_3(= 9), the game proceeds as follows:

• Takahashi takes the card with 13.
• Aoki takes the card with 7.
• Takahashi takes the card with 11.
• Aoki takes the card with 5.
• Takahashi takes the card with 3.

Thus, 13 + 11 + 3 = 27 should be printed on the third line.

Sample Input 2

4 3
10 20 30 40
2
34
34

Sample Output 2

70
60
60

Problem Statement

The server in company A has a structure where N devices numbered 1, 2, ..., N are connected with N - 1 cables. The i-th cable connects Device U_i and Device V_i. Any two different devices are connected through some number of cables.

Each device v (1 \leq v \leq N) has a non-zero integer A_v, which represents the following:

• If A_v < 0, Device v is a computer that consumes an electric power of -A_v.
• If A_v > 0, Device v is a battery that supplies an electric power of A_v.

You have decided to disconnect some number of cables (possibly zero) to disable the server. When some cables are disconnected, the devices will be divided into some number of connected components. The server will be disabled if all of these connected components satisfy one of the following conditions:

• There is no computer in the connected component. That is, A_v is positive for every device v that belongs to the connected component.
• There is not enough supply of electric power in the connected component. That is, the sum of A_v over all devices v that belong to the connected component is negative.

At least how many cables do you need to disconnect in order to disable the server?

Constraints

• 1 \leq N \leq 5 000
• 1 \leq |A_i| \leq 10^9 (1 \leq i \leq N)
• 1 \leq U_i, V_i \leq N (1 \leq i \leq N - 1)
• U_i \neq V_i (1 \leq i \leq N - 1)
• Any two different devices are connected through some number of cables.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1

We should disconnect the cable connecting Device 1 and Device 2.

Sample Input 2

4
1 2 3 4
1 2
1 3
1 4

Sample Output 2

0

Sample Input 3

6
10 -1 10 -1 10 -1
1 2
2 3
3 4
4 5
5 6

Sample Output 3

5

Sample Input 4

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

Sample Output 4

3

Sample Input 5

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

Sample Output 5

3