Problem Statement

Takahashi is a librarian at a university library. The library has N books, and each book i (1 \leq i \leq N) has a "difficulty" P_i assigned to it. Different books may have the same difficulty, but they are treated as separate books.

To support students' learning, the library issues M types of "viewing permits." Each viewing permit j (1 \leq j \leq M) has a "permit level" L_j, and a student holding this permit can view all books with difficulty L_j or less.

One day, Aoki visits this library. Aoki holds K viewing permits, numbered T_1, T_2, \ldots, T_K.

Aoki wants to read all books that can be viewed with any of his viewing permits. That is, the target books are those in the union of the sets of books viewable by each of his K viewing permits. Even if the same book can be viewed by multiple viewing permits, it is counted as one book.

Find the sum of difficulties of all books that Aoki can view.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq K \leq M
• 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq L_j \leq 10^9 (1 \leq j \leq M)
• 1 \leq T_k \leq M (1 \leq k \leq K)
• T_1, T_2, \ldots, T_K are all distinct
• All input values are integers

Sample Input 1

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

Sample Output 1

21

Sample Input 2

6 4 3
10 20 30 40 50 60
25 15 45 35
2 3 4

Sample Output 2

100

Sample Input 3

10 5 2
100 200 300 400 500 600 700 800 900 1000
150 350 550 750 950
3 5

Sample Output 3

4500

Problem Statement

Takahashi decided to implement a simple compression algorithm to efficiently store a large amount of log data.

The compression rules Takahashi devised are as follows:

Given a string S consisting of lowercase English letters, replace each consecutive sequence of the same character with "that character once + the count of consecutive occurrences." However, if the count is 1, omit the count and output only the character.

For example, the string aaabbc is compressed as follows:

• aaa → a3 (3 consecutive a's)
• bb → b2 (2 consecutive b's)
• c → c (only 1 c, so the count is omitted)
• Result: a3b2c

This compression method is called run-length encoding, and it is effective for data where the same character appears consecutively.

For Takahashi, please output the result of compressing the given string according to the rules above.

Constraints

• 1 \leq |S| \leq 2 \times 10^5
• S consists only of lowercase English letters

Sample Input 1

aaabbc

Sample Output 1

a3b2c

Sample Input 2

abcde

Sample Output 2

abcde

Sample Input 3

aaabbbbccdddddeeefghhhh

Sample Output 3

a3b4c2d5e3fgh4

Sample Input 4

zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbccccccccccddddddddddddeeeeeeeeeeffffffffgggggggggggggghhhhhhhhhiiiiiiiiiiijjjjjjjjkkkkkkkkkkklllllllllllmmmmmmmmmnnnnnnnnnnooooooooooppppppppppqqqqqqqqqqrrrrrrrrrrssssssssssttttttttttuuuuuuuuuuvvvvvvvvvvwwwwwwwwwwxxxxxxxxxxyyyyyyyyyyzzzzzzzzzz

Sample Output 4

z51a20b15c10d12e10f8g14h9i11j8k11l11m9n10o10p10q10r10s10t10u10v10w10x10y10z10

Sample Input 5

a

Sample Output 5

a

Problem Statement

Takahashi, as the person in charge of new business at his company, is trying to select which projects to execute from N project proposals. Each project is either executed or not, and the same project cannot be executed more than once. It is also allowed to select no projects at all.

Executing each project i (1 \leq i \leq N) requires a cost of C_i ten-thousand yen, and yields a profit of P_i ten-thousand yen. Here, profit and cost are independent values, and the objective is to maximize the total profit. Cost is only relevant to the budget constraint and is not subtracted from the profit.

However, some pairs of projects conflict with each other due to competing team assignments or shared equipment, and cannot both be selected at the same time. There are M such conflict relationships, and the j-th (1 \leq j \leq M) conflict relationship indicates that both project U_j and project V_j cannot be selected simultaneously.

Takahashi's budget limit is K ten-thousand yen. Find the maximum total profit of the selected projects such that the total cost of the selected projects is at most K ten-thousand yen and no conflict relationship has both projects selected simultaneously.

In other words, letting S be the set of selected projects, find the maximum value of \displaystyle\sum_{i \in S} P_i subject to all of the following conditions:

• \displaystyle\sum_{i \in S} C_i \leq K
• For all j (1 \leq j \leq M), U_j and V_j are not both contained in S (i.e., \{U_j, V_j\} \not\subseteq S)

If no projects are selected (i.e., S is the empty set), the total profit is 0.

Constraints

• 1 \leq N \leq 18
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq K \leq 10^5
• 1 \leq C_i \leq 10^5 (1 \leq i \leq N)
• 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
• The same conflict relationship is not given more than once
• All inputs are integers

Sample Input 1

3 1 100
50 80
60 90
40 50
1 2

Sample Output 1

140

Sample Input 2

5 3 200
30 100
50 150
40 120
60 200
80 180
1 2
2 3
4 5

Sample Output 2

420

Sample Input 3

8 6 500
100 500
80 400
120 600
90 450
70 350
110 550
60 300
150 800
1 2
1 3
2 4
3 4
5 6
7 8

Sample Output 3

2350

Problem Statement

Takahashi lives in a city consisting of N locations and M roads. Each location is numbered from 1 to N. The roads are bidirectional, and the i-th road connects location u_i and location v_i, taking w_i time to traverse. There may be multiple roads between the same pair of locations.

One day, a large-scale disaster occurs, and Takahashi must evacuate from location 1 (his home) to location N (the evacuation shelter). K locations in the city are flooded, and the flooded locations are numbered g_1, g_2, \ldots, g_K (when K = 0, there are no flooded locations).

Takahashi starts at location 1 and travels along roads to reach location N. His route is represented as a pair of a sequence of locations and a sequence of roads used. Specifically, it consists of a sequence of locations p_0, p_1, p_2, \ldots, p_L (L \geq 1) and, for each i (1 \leq i \leq L), a choice of road e_i that directly connects location p_{i-1} and location p_i. Here, p_0 = 1 and p_L = N. Visiting the same location multiple times is allowed.

The total time when Takahashi travels along this route is defined as the sum of the following two values:

1. Travel time: The sum of the traversal times of all roads used along the route. That is, \displaystyle\sum_{i=1}^{L} w_{e_i} (where w_{e_i} is the traversal time of road e_i).
2. Flooding penalty: For each element in the location sequence p_0, p_1, \ldots, p_L, if that location is a flooded location, an additional time of T is incurred. This applies to the starting location p_0 and the destination p_L as well. If the same flooded location is visited multiple times, the additional time T is added for each occurrence in the location sequence. The flooding penalty is the sum of all such additions.

Find the minimum total time for Takahashi to travel from location 1 to location N. It is guaranteed that location N is reachable from location 1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq K \leq N
• 0 \leq T \leq 10^9
• 1 \leq u_i, v_i \leq N (1 \leq i \leq M)
• u_i \neq v_i (1 \leq i \leq M)
• 1 \leq w_i \leq 10^9 (1 \leq i \leq M)
• There may be multiple roads between the same pair of locations
• 1 \leq g_j \leq N (1 \leq j \leq K)
• All g_j are distinct
• Location N is reachable from location 1
• All input values are integers

Sample Input 1

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

Sample Output 1

11

Sample Input 2

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

Sample Output 2

20

Sample Input 3

8 10 0 100
1 2 2
1 3 10
2 5 3
3 4 5
4 6 2
5 7 4
6 7 8
7 8 1
3 5 6
6 8 12

Sample Output 3

10

Problem Statement

Takahashi is a librarian at a library. The library has N shelves arranged in a row, numbered 1, 2, \ldots, N from left to right.

One day, he performs the task of returning M books to the shelves. The order of returning books is fixed: he returns them one by one in order — the 1st book, the 2nd book, \ldots, the Mth book. The shelf number to which the i-th (1 \leq i \leq M) book should be returned is G_i. Note that multiple books may be returned to the same shelf.

Each time Takahashi returns the i-th (1 \leq i \leq M) book to its shelf, he records a value L_i defined as follows:

• L_i: Among the M - i books scheduled to be returned as the (i+1)-th, (i+2)-th, \ldots, M-th books (that is, all books that have not yet been returned to the shelves at the moment the i-th book is returned), the number of books whose destination shelf number is less than G_i. When i = M, there are 0 such books, so L_M = 0.

After the day's work is finished, Takahashi must write the total of the recorded values L_1 + L_2 + \cdots + L_M in his report.

Given the number of shelves N, the number of books M, and the destination shelf number G_i for each book, find the value of L_1 + L_2 + \cdots + L_M.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq G_i \leq N (1 \leq i \leq M)
• All input values are integers

Sample Input 1

5 4
3
1
4
2

Sample Output 1

3

Sample Input 2

3 5
2
3
1
2
1

Sample Output 2

6

Sample Input 3

10 8
5
3
8
1
7
2
6
4

Sample Output 3

15

Sample Input 4

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

Sample Output 4

63

Sample Input 5

1 1
1

Sample Output 5

0