Problem Statement

Takahashi works as a general information clerk at a city hall. At this city hall, applications for procedures flood in at the end of the fiscal year, so efficient counter management is required.

The city hall has N counters, numbered from 1 to N. Each counter i (1 \leq i \leq N) has a daily reception limit C_i, meaning it can accept up to C_i applications per day. At the beginning of the day, the number of accepted applications at every counter is 0.

On a certain day, M applications arrived in order. The j-th application (1 \leq j \leq M) is from a citizen who wishes to have their procedure handled at counter T_j.

The applications are processed one by one in the order j = 1, 2, \ldots, M. Each application j is processed as follows:

• If the current number of accepted applications at the desired counter T_j is less than the reception limit C_{T_j}, the application is accepted, and the number of accepted applications at counter T_j increases by 1.
• If the current number of accepted applications at the desired counter T_j is equal to the reception limit C_{T_j} (i.e., the reception limit has been reached), the application is rejected. In the case of rejection, the number of accepted applications does not change, and the application is not redirected to any other counter.

After processing all applications, find the total number of accepted applications.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq T_j \leq N (1 \leq j \leq M)
• All input values are integers

Sample Input 1

3 5
2 1 3
1
2
1
1
2

Sample Output 1

3

Sample Input 2

4 10
3 2 1 4
1
2
3
4
1
2
3
1
4
4

Sample Output 2

9

Sample Input 3

5 15
1000000000 1 2 3 1
1
1
1
2
2
3
3
3
4
4
4
4
5
5
1

Sample Output 3

11

Problem Statement

Takahashi is investigating a railway line. This line has N stations, numbered from 1 to N.

This line has a special structure. From station i (1 \leq i \leq N-1), only a train heading to station P_i is operated. Here, P_i is an integer between 1 and N, inclusive, that is different from i. Station N is the final destination, and no trains depart from station N.

Takahashi starts at station 1 and repeatedly boards the only train available at each station, aiming to reach station N. The journey ends when he arrives at station N.

The input is given such that starting from station 1 and repeating the above process, he will always reach station N in a finite number of moves without visiting the same station twice.

Find the number of stations visited from station 1 until reaching station N. Include both the departure station (station 1) and the arrival station (station N) in the count.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq N (1 \leq i \leq N-1)
• P_i \neq i (1 \leq i \leq N-1)
• It is guaranteed that station N can be reached from station 1 without visiting the same station twice
• All input values are integers

Sample Input 1

5
2 4 5 5

Sample Output 1

4

Sample Input 2

8
3 5 7 2 8 4 6

Sample Output 2

8

Sample Input 3

10
2 3 4 5 6 7 8 9 10

Sample Output 3

10

Problem Statement

Takahashi manages N flower beds arranged in a row in his garden. The flower beds are numbered 1, 2, \ldots, N from left to right, and the current moisture level of the soil in flower bed i (1 \leq i \leq N) is A_i.

Since he will have guests tomorrow, Takahashi wants to make all flower beds have a moisture level of at least the target value T so that the flowers bloom beautifully. It is fine if the moisture level exceeds T.

Takahashi can perform the following operation any number of times (possibly 0 times):

• Operation: Choose an integer l satisfying 1 \leq l \leq N - K + 1, and water the K consecutive flower beds from flower bed l to flower bed l + K - 1 using a sprinkler. This increases the moisture level of each of those K flower beds by 1. Each operation costs C yen in water charges.

The value of l chosen in each operation is arbitrary, and the same value of l may be chosen in different operations.

Find the minimum total water cost (in yen) required to make the moisture level of all flower beds at least T.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq T \leq 10^9
• 1 \leq C \leq 10^9
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers
• It is guaranteed that the answer is at most 2^{63} - 1 (i.e., it fits in a signed 64-bit integer type)

Sample Input 1

5 3 10 100
8 7 9 12 11

Sample Output 1

300

Sample Input 2

8 2 15 50
12 10 14 13 11 15 9 16

Sample Output 2

750

Sample Input 3

10 4 20 1000
18 15 12 19 17 14 16 20 13 21

Sample Output 3

15000

Problem Statement

Takahashi is in charge of managing meeting room reservations at his company. The company has only 1 meeting room, and at most 1 meeting can be held at any given time.

One day, N meeting reservation requests arrived. The i-th meeting starts at time L_i and ends at time R_i (L_i < R_i). Since there is only one meeting room, meetings with overlapping time slots cannot be held simultaneously.

Here, two meetings i and j are said to "overlap" if the intervals (L_i, R_i) and (L_j, R_j) have a common part, that is, if L_i < R_j and L_j < R_i both hold. If the end time of one meeting coincides with the start time of another meeting (for example, R_i = L_j), they are considered non-overlapping and can be held consecutively.

Takahashi wants to schedule as many meetings as possible. Find the maximum number of meetings that can be selected such that no two of them overlap.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq L_i < R_i \leq 10^9
• All input values are integers.

Sample Input 1

5
1 5
3 8
1 3
5 8
2 6

Sample Output 1

2

Sample Input 2

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

Sample Output 2

5

Sample Input 3

12
0 100
50 150
100 200
200 500
150 300
300 600
500 700
600 800
700 800
750 900
1000 1000000000
999999999 1000000000

Sample Output 3

6

Problem Statement

Takahashi is in charge of displaying N paintings in a row at an art museum exhibition.

Each painting is numbered from 1 to N, and painting i has a tone value of P_i. When the paintings are arranged in a row, the greater the difference in tone values between adjacent paintings, the more impact it gives to the viewers.

The exhibition space has N positions arranged from left to right, and exactly one painting is placed at each position. Between adjacent positions, there are partition walls, totaling N - 1 partition walls. The partition wall between the i-th position from the left and the (i + 1)-th position from the left has a weight W_i. Viewers are more likely to stop in front of walls with larger weights, so the impact of the pair of paintings placed adjacent to such a wall is evaluated more highly.

Takahashi uses all N paintings exactly once and places them at the N positions. Let Q_i denote the number of the painting placed at the i-th position from the left. Then (Q_1, Q_2, \ldots, Q_N) is a permutation of (1, 2, \ldots, N). The overall evaluation score of the exhibition is calculated as

\sum_{i=1}^{N-1} |P_{Q_i} - P_{Q_{i+1}}| \times W_i

where P_{Q_i} represents the tone value of painting Q_i placed at the i-th position from the left.

Takahashi wants to determine the arrangement of paintings that maximizes the evaluation score. Given the tone values P_1, P_2, \ldots, P_N of the N paintings and the weights W_1, W_2, \ldots, W_{N-1} of the N - 1 partition walls, find the maximum evaluation score among all possible arrangements.

Constraints

• 2 \leq N \leq 16
• 1 \leq P_i \leq 10^7 (1 \leq i \leq N)
• 1 \leq W_i \leq 10^7 (1 \leq i \leq N-1)
• All input values are integers.

Sample Input 1

3
1 5 3
2 4

Sample Output 1

20

Sample Input 2

4
10 10 20 30
1 3 2

Sample Output 2

110

Sample Input 3

8
8 1 14 7 20 3 11 17
5 2 9 1 4 8 3

Sample Output 3

422

Sample Input 4

16
42 7 81 19 63 5 97 28 54 12 76 33 88 21 69 40
3 11 2 17 5 13 7 19 4 23 6 29 8 31 10

Sample Output 4

11913

Sample Input 5

2
1 10000000
10000000

Sample Output 5

99999990000000