Problem Statement

We have N cups of ice cream.
The flavor and deliciousness of the i-th cup are F_i and S_i, respectively (S_i is an even number).

You will choose and eat two of the N cups.
Your satisfaction here is defined as follows.

• Let s and t (s \ge t) be the deliciousness of the eaten cups.
  • If the two cups have different flavors, your satisfaction is \displaystyle s+t.
  • Otherwise, your satisfaction is \displaystyle s + \frac{t}{2}.

Find the maximum achievable satisfaction.

Constraints

• All input values are integers.
• 2 \le N \le 3 \times 10^5
• 1 \le F_i \le N
• 2 \le S_i \le 10^9
• S_i is even.

Sample Input 1

4
1 4
2 10
2 8
3 6

Sample Output 1

16

Consider eating the second and fourth cups.

• The second cup has a flavor of 2 and deliciousness of 10.
• The fourth cup has a flavor of 3 and deliciousness of 6.
• Since they have different flavors, your satisfaction is 10+6=16.

Thus, you can achieve the satisfaction of 16.
You cannot achieve a satisfaction greater than 16.

Sample Input 2

4
4 10
3 2
2 4
4 12

Sample Output 2

17

Consider eating the first and fourth cups.

• The first cup has a flavor of 4 and deliciousness of 10.
• The fourth cup has a flavor of 4 and deliciousness of 12.
• Since they have the same flavor, your satisfaction is 12+\frac{10}{2}=17.

Thus, you can achieve the satisfaction of 17.
You cannot achieve a satisfaction greater than 17.

Problem Statement

There are N stations on a certain line operated by AtCoder Railway. The i-th station (1 \leq i \leq N) from the starting station is named S_i.

Local trains stop at all stations, while express trains may not. Specifically, express trains stop at only M \, (M \leq N) stations, and the j-th stop (1 \leq j \leq M) is the station named T_j.
Here, it is guaranteed that T_1 = S_1 and T_M = S_N, that is, express trains stop at both starting and terminal stations.

For each of the N stations, determine whether express trains stop at that station.

Constrains

• 2 \leq M \leq N \leq 10^5
• N and M are integers.
• S_i (1 \leq i \leq N) is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
• S_i \neq S_j \, (i \neq j)
• T_1 = S_1 and T_M = S_N.
• (T_1, \dots, T_M) is obtained by removing zero or more strings from (S_1, \dots, S_N) and lining up the remaining strings without changing the order.

Sample Input 1

5 3
tokyo kanda akiba okachi ueno
tokyo akiba ueno

Sample Output 1

Yes
No
Yes
No
Yes

Sample Input 2

7 7
a t c o d e r
a t c o d e r

Sample Output 2

Yes
Yes
Yes
Yes
Yes
Yes
Yes

Express trains may stop at all stations.

Problem Statement

We have N distinct points on a two-dimensional plane, numbered 1,2,\ldots,N. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).

How many rectangles are there whose vertices are among the given points and whose edges are parallel to the x- or y-axis?

Constraints

• 4 \leq N \leq 2000
• 0 \leq x_i, y_i \leq 10^9
• (x_i,y_i) \neq (x_j,y_j) (i \neq j)
• All values in input are integers.

Sample Input 1

6
0 0
0 1
1 0
1 1
2 0
2 1

Sample Output 1

3

There are three such rectangles:

the rectangle whose vertices are Points 1, 2, 3, 4,

the rectangle whose vertices are Points 1, 2, 5, 6,

and the rectangle whose vertices are Points 3, 4, 5, 6.

Sample Input 2

4
0 1
1 2
2 3
3 4

Sample Output 2

0

Sample Input 3

7
0 1
1 0
2 0
2 1
2 2
3 0
3 2

Sample Output 3

1

Problem Statement

Takahashi is playing sugoroku, a board game.

The board has N+1 squares, numbered 0 to N. Takahashi starts at square 0 and goes for square N.

The game uses a roulette wheel with M numbers from 1 to M that appear with equal probability. Takahashi spins the wheel and moves by the number of squares indicated by the wheel. If this would send him beyond square N, he turns around at square N and goes back by the excessive number of squares.

For instance, assume that N=4 and Takahashi is at square 3. If the wheel shows 4, the excessive number of squares beyond square 4 is 3+4-4=3. Thus, he goes back by three squares from square 4 and arrives at square 1.

When Takahashi arrives at square N, he wins and the game ends.

Find the probability, modulo 998244353, that Takahashi wins when he may spin the wheel at most K times.

Constraints

• M \leq N \leq 1000
• 1 \leq M \leq 10
• 1 \leq K \leq 1000
• All values in the input are integers.

Sample Input 1

2 2 1

Sample Output 1

499122177

Takahashi wins in one spin if the wheel shows 2. Therefore, the probability of winning is \frac{1}{2}.

We have 2\times 499122177 \equiv 1 \pmod{998244353}, so the answer to be printed is 499122177.

Sample Input 2

10 5 6

Sample Output 2

184124175

Sample Input 3

100 1 99

Sample Output 3

0

Problem Statement

Takahashi is at the origin of a number line. Takahashi wants to reach the goal at coordinate X.

Also, there are N walls and N hammers on the number line.

• At coordinates Y_1,Y_2,\dots,Y_N are walls of types 1,2,\dots,N, respectively.
  • Initially, Takahashi cannot get over the walls.
• At coordinates Z_1,Z_2,\dots,Z_N are hammers of types 1,2,\dots,N, respectively.
  • When he arrives at a coordinate with a hammer, he obtains the hammer.
  • The hammer of type i is dedicated to destroying the wall of type i. After he obtains the hammer of type i, he can destroy the wall of type i and get over it.

Determine if he can reach the goal. If he can, find the minimum distance he travels.

Constraints

• All values in the input are integers.
• 1 \le N \le 1500
• 1 \le |X|,|Y_i|,|Z_i| \le 10^9
• The (2 \times N + 1) coordinates X,Y_i and Z_i are distinct.

Sample Input 1

3 10
-2 8 -5
5 -10 3

Sample Output 1

40

Takahashi can reach the goal by traveling a distance of 40 as follows, which is the minimum possible:

• He starts at coordinate 0.
• He moves to coordinate 3 to obtain the hammer of type 3.
• He moves to coordinate 5 to obtain the hammer of type 1.
• He moves to coordinate -2 to destroy the wall of type 1.
• He moves to coordinate -5 to destroy the wall of type 3.
• He moves to coordinate -10 to obtain the hammer of type 2.
• He moves to coordinate 8 to destroy the wall of type 2.
• He moves to coordinate 10, which is the goal.

Sample Input 2

5 -1
10 -20 30 -40 50
-10 20 -30 40 -50

Sample Output 2

1

It may not be required that he obtains a hammer or destroys a wall to reach the goal.

Sample Input 3

1 100
30
60

Sample Output 3

-1

Takahashi cannot obtain the hammer of type 1, and neither can he reach the goal.

Sample Input 4

4 865942261
703164879 -531670946 -874856231 -700164975
-941120316 599462305 -649785130 665402307

Sample Output 4

4078987507