Problem Statement

Find a length-N string that satisfies all of the following conditions:

• Each character is - or =.
• It is a palindrome.
• It contains exactly one or exactly two =s. If it contains two =s, they are adjacent.

Such a string is unique.

Constraints

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

Sample Input 1

4

Sample Output 1

-==-

Sample Input 2

7

Sample Output 2

---=---

Problem Statement

There are N items. You are given strings T and A of length N that represent which items Takahashi and Aoki want, respectively. Let T_i and A_i be the i-th (1\leq i\leq N) characters of T and A, respectively.

Takahashi wants the i-th item when T_i is o, and does not want the i-th item when T_i is x. Similarly, Aoki wants the i-th item when A_i is o, and does not want the i-th item when A_i is x.

Determine whether there exists an item that both of them want.

Constraints

• 1\leq N\leq 100
• N is an integer.
• T and A are strings of length N consisting of o and x.

Sample Input 1

4
oxoo
xoox

Sample Output 1

Yes

The third item is wanted by both of them, so output Yes.

Sample Input 2

5
xxxxx
ooooo

Sample Output 2

No

There is no item that both of them want, so output No.

Sample Input 3

10
xoooxoxxxo
ooxooooxoo

Sample Output 3

Yes

Problem Statement

Takahashi is exploring a cave in a video game.

The cave consists of N rooms arranged in a row. The rooms are numbered Room 1,2,\ldots,N from the entrance.

Takahashi is initially in Room 1, and the time limit is T.
For each 1 \leq i \leq N-1, he may consume a time of A_i to move from Room i to Room (i+1). There is no other way to move between rooms. He cannot make a move that makes the time limit 0 or less.

There are M bonus rooms in the cave. The i-th bonus room is Room X_i; when he arrives at the room, the time limit increases by Y_i.

Can Takahashi reach Room N?

Constraints

• 2 \leq N \leq 10^5
• 0 \leq M \leq N-2
• 1 \leq T \leq 10^9
• 1 \leq A_i \leq 10^9
• 1 < X_1 < \ldots < X_M < N
• 1 \leq Y_i \leq 10^9
• All values in input are integers.

Sample Input 1

4 1 10
5 7 5
2 10

Sample Output 1

Yes

• Takahashi is initially in Room 1, and the time limit is 10.
• He consumes a time of 5 to move to Room 2. Now the time limit is 5. Then, the time limit increases by 10; it is now 15.
• He consumes a time of 7 to move to Room 3. Now the time limit is 8.
• He consumes a time of 5 to move to Room 4. Now the time limit is 3.

Sample Input 2

4 1 10
10 7 5
2 10

Sample Output 2

No

He cannot move from Room 1 to Room 2.

Problem Statement

Iroha has a sequence of positive integers A = (A_1, A_2, \dots, A_N) of length N (N \ge 1).
She generated a string S using A as follows:

• Start with S = |.
• For i = 1, 2, \dots, N, perform the following operations in order:
  • Append A_i copies of - to the end of S.
  • Then, append one | to the end of S.

Given the generated string S, reconstruct the sequence A.

Constraints

• S is a string of length between 3 and 100, inclusive, generated by the method in the problem statement.
• A is a sequence of positive integers of length at least 1.

Sample Input 1

|---|-|----|-|-----|

Sample Output 1

3 1 4 1 5

S = |---|-|----|-|-----| is generated by A = (3, 1, 4, 1, 5).

Sample Input 2

|----------|

Sample Output 2

10

Sample Input 3

|-|-|-|------|

Sample Output 3

1 1 1 6

Problem Statement

You are given N strings S_1,S_2,\dots,S_N consisting of lowercase English alphabets.

Consider choosing some number of strings from S_1,S_2,\dots,S_N.

Find the maximum number of distinct alphabets that satisfy the following condition: "the alphabet is contained in exactly K of the chosen strings."

Constraints

• 1 \le N \le 15
• 1 \le K \le N
• N and K are integers.
• S_i is a non-empty string consisting of lowercase English alphabets.
• For each integer i such that 1 \le i \le N, S_i does not contain two or more same alphabets.
• If i \neq j, then S_i \neq S_j.

Sample Input 1

4 2
abi
aef
bc
acg

Sample Output 1

3

When S_1,S_3, and S_4 are chosen, a,b, and c occur in exactly two of the strings.

There is no way to choose strings so that 4 or more alphabets occur in exactly 2 of the strings, so the answer is 3.

Sample Input 2

2 2
a
b

Sample Output 2

0

You cannot choose the same string more than once.

Sample Input 3

5 2
abpqxyz
az
pq
bc
cy

Sample Output 3

7

Problem Statement

Takahashi can combine a head part and a body part to create a robot. A robot falls over if the weight of the head part is greater than the weight of the body part.

Currently, he has N head parts and M body parts. The weight of the i-th (1\le i\le N) head part is H _ i grams, and the weight of the i-th (1\le i\le M) body part is B _ i grams.

He wants to create a total of K robots that do not fall over by appropriately combining the parts he has. Determine whether he can achieve his goal by combining the parts well.

Here, a part cannot be used to create multiple robots, and two or more head parts (or two or more body parts) cannot be used to create one robot.

Constraints

• 1\le N\le2\times10 ^ 5
• 1\le M\le2\times10 ^ 5
• 1\le K\le\min\lbrace N,M\rbrace
• 1\le H _ i\le10 ^ 9\ (1\le i\le N)
• 1\le B _ i\le10 ^ 9\ (1\le i\le M)
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

If we denote combining the i-th head part and the j-th body part as (i,j), then Takahashi can create three robots that do not fall over by combining them as (1,2),(2,4),(3,6), for example.

Thus, print Yes.

Sample Input 2

1 1 1
43
1

Sample Output 2

No

His head part is too heavy, so he cannot create any robot that does not fall over.

Sample Input 3

1 1 1
100
100

Sample Output 3

Yes

Note that a robot does not fall over if the head and body have equal weights.

Sample Input 4

12 15 12
748 169 586 329 972 529 432 519 408 587 138 249
656 114 632 299 984 755 404 772 155 506 832 854 353 465 387

Sample Output 4

Yes

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges. Each vertex i\,(1\leq i \leq N) has a weight A_i. Each edge j\,(1\leq j \leq M) connects vertices U_j and V_j bidirectionally and has a weight B_j.

The weight of a path in this graph is defined as the sum of the weights of the vertices and edges that appear on the path.

For each i=2,3,\dots,N, solve the following problem:

• Find the minimum weight of a path from vertex 1 to vertex i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq U_j < V_j \leq N
• (U_i, V_i) \neq (U_j, V_j) if i \neq j.
• The graph is connected.
• 0 \leq A_i \leq 10^9
• 0 \leq B_j \leq 10^9
• All input values are integers.

Sample Input 1

3 3
1 2 3
1 2 1
1 3 6
2 3 2

Sample Output 1

4 9

Consider the paths from vertex 1 to vertex 2. The weight of the path 1 \to 2 is A_1 + B_1 + A_2 = 1 + 1 + 2 = 4, and the weight of the path 1 \to 3 \to 2 is A_1 + B_2 + A_3 + B_3 + A_2 = 1 + 6 + 3 + 2 + 2 = 14. The minimum weight is 4.

Consider the paths from vertex 1 to vertex 3. The weight of the path 1 \to 3 is A_1 + B_2 + A_3 = 1 + 6 + 3 = 10, and the weight of the path 1 \to 2 \to 3 is A_1 + B_1 + A_2 + B_3 + A_3 = 1 + 1 + 2 + 2 + 3 = 9. The minimum weight is 9.

Sample Input 2

2 1
0 1
1 2 3

Sample Output 2

4

Sample Input 3

5 8
928448202 994752369 906965437 942744902 907560126
2 5 975090662
1 2 908843627
1 5 969061140
3 4 964249326
2 3 957690728
2 4 942986477
4 5 948404113
1 3 988716403

Sample Output 3

2832044198 2824130042 4696218483 2805069468

Note that the answers may not fit in a 32-bit integer.

Problem Statement

Takahashi is about to play a game where he fights N monsters in order. Initially, Takahashi's health is H and his magic power is M.

For the i-th monster he fights, he can choose one of the following actions:

• Fight without using magic. This can only be chosen when his health is at least A_i, and his health decreases by A_i and the monster is defeated.
• Fight using magic. This can only be chosen when his magic power is at least B_i, and his magic power decreases by B_i and the monster is defeated.

The game ends when all N monsters are defeated or when he cannot take any action. What is the maximum number of monsters he can defeat before the game ends?

Constraints

• 1 \leq N \leq 3000
• 1 \leq H,M \leq 3000
• 1 \leq A_i,B_i \leq 3000
• All input values are integers.

Sample Input 1

4 10 14
5 8
5 6
7 9
99 99

Sample Output 1

3

By taking the following actions, Takahashi can defeat 3 monsters before the game ends.

• Initially, his health is 10 and his magic power is 14.
• Fight the 1st monster without using magic. His health decreases by 5, becoming health 5 and magic power 14.
• Fight the 2nd monster without using magic. His health decreases by 5, becoming health 0 and magic power 14.
• Fight the 3rd monster using magic. His magic power decreases by 9, becoming health 0 and magic power 5.
• For the 4th monster, he cannot choose either action, so the game ends.

Sample Input 2

3 3000 3000
3 3
3 3
3 3

Sample Output 2

3

He may be able to defeat all monsters.

Sample Input 3

10 8 8
2 2
2 3
2 2
1 2
2 3
1 2
3 3
3 2
3 1
3 2

Sample Output 3

9

Problem Statement

Given is an undirected graph with N+1 vertices.
The vertices are called Vertex 0, Vertex 1, \ldots, Vertex N.

For each i=1,2,\ldots,N, the graph has an undirected edge with a weight of A_i connecting Vertex 0 and Vertex i.

Additionally, for each i=1,2,\ldots,N, the graph has an undirected edge with a weight of B_i connecting Vertex i and Vertex i+1. (Here, Vertex N+1 stands for Vertex 1.)

The graph has no edge other than these 2N edges above.

Let us delete some of the edges from this graph so that the graph will be bipartite.
What is the minimum total weight of the edges that have to be deleted?

Constraints

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

Sample Input 1

5
31 4 159 2 65
5 5 5 5 10

Sample Output 1

16

Deleting the edge connecting Vertices 0,2 (weight: 4), the edge connecting Vertices 0,4 (weight: 2), and the edge connecting Vertices 1,5 (weight: 10) makes the graph bipartite.

Sample Input 2

4
100 100 100 1000000000
1 2 3 4

Sample Output 2

10