Problem Statement

Takahashi is in charge of managing packages at a logistics company's warehouse. Today, N packages were scheduled to arrive, but M of them were cancelled by the sender and will not be delivered.

In the warehouse, each package is assigned a management number from 1 to N. The weight of the package with management number i is T_i grams (1 \leq i \leq N). The management numbers of the M cancelled packages are given as D_1, D_2, \ldots, D_M. Note that the same package is never cancelled more than once.

To store the delivered packages on shelves, Takahashi decided to convert the weights into a unit called "units" and record them. 1 unit corresponds to K grams. The number of units for each package is defined as the weight (in grams) of that package divided by K, rounded down to the nearest integer. That is, the number of units for the package with management number i is \lfloor T_i / K \rfloor.

For each package that was not cancelled and actually arrived (i.e., packages whose management numbers are not any of D_1, D_2, \ldots, D_M), compute the number of units and output their total sum.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq N
• 1 \leq K \leq 10^9
• 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq D_j \leq N (1 \leq j \leq M)
• D_1, D_2, \ldots, D_M are all distinct
• All input values are integers

Sample Input 1

5 2 3
10 7 8 5 6
2 4

Sample Output 1

7

Sample Input 2

4 1 5
3 12 7 20
3

Sample Output 2

6

Sample Input 3

10 3 100
250 99 450 1000 50 333 678 812 999 10
2 5 9

Sample Output 3

33

Sample Input 4

15 5 7
100 49 35 77 64 21 88 53 42 99 15 70 28 56 91
1 5 8 12 15

Sample Output 4

72

Sample Input 5

1 0 1000000000
999999999

Sample Output 5

0

Problem Statement

Takahashi is the coach of a team competing in a programming contest.

For this tournament, N players have gathered as candidates. Each player is assigned a number from 1 to N, and the skill value of player i is A_i.

According to the tournament rules, a team must consist of exactly K members. Basically, Takahashi wants to select members in descending order of skill value, but there is one special circumstance.

Aoki is Takahashi's childhood friend and is participating as one of the candidate players. Aoki's player number is T. Since Takahashi has promised to include Aoki on the team, he decides to use the following member selection method:

1. First, Aoki (player T) is always included as a team member.
2. The remaining K - 1 members are selected from the N - 1 candidate players (excluding Aoki) by choosing the K - 1 players with the highest skill values. However, if K = 1, the team consists of only Aoki.

Find the total skill value of the K members selected under this rule.

Note that if there are multiple players with equal skill values at the selection boundary, the total skill value is the same regardless of which players are chosen, so the answer is uniquely determined.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq T \leq N
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5 3 2
10 5 8 3 7

Sample Output 1

23

Sample Input 2

7 4 5
100 250 180 90 120 300 75

Sample Output 2

850

Sample Input 3

10 5 7
500000000 300000000 800000000 150000000 600000000 450000000 200000000 900000000 350000000 700000000

Sample Output 3

3200000000

Problem Statement

Takahashi is in charge of organizational management at a large company. The company has N departments, each numbered from 1 to N. Department 1 is the headquarters that oversees the entire company.

The company's organizational structure is represented as a rooted tree, with department 1 (headquarters) as the root. The parent of department i (2 \leq i \leq N) is department P_i. In other words, department i is a direct subdivision of department P_i.

One day, the management decided to dismantle department K in order to streamline the organization. The dismantling removes department K itself and all departments that are its descendants. Here, the descendants of department K refer to all departments that can be reached by recursively following children of department K in the rooted tree — that is, children, children of children, and so on (department K itself is not included in its descendants).

Determine the number of departments remaining in the company after the dismantling. Note that if K = 1, all departments in the company are subject to dismantling, so the answer is 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N
• 1 \leq P_i < i (2 \leq i \leq N)
• All input values are integers.

Sample Input 1

5 3
1 1 3 3

Sample Output 1

2

Sample Input 2

8 2
1 1 2 2 3 5 5

Sample Output 2

3

Sample Input 3

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

Sample Output 3

9

Problem Statement

Takahashi is in charge of managing a meeting room at a company. This meeting room operates by dividing each day into T time slots (time slots 1, 2, \ldots, T), and only 1 meeting can be assigned to each time slot at a time.

One day, N requests for meeting room usage were received.

The i-th request (1 \leq i \leq N) is to use the meeting room for consecutive time slots from time slot L_i to time slot R_i (inclusive). If the i-th request is approved, the company earns a profit of V_i yen.

Takahashi will select and approve 0 or more of these N requests. However, the same request cannot be approved more than once, and for any 2 approved requests, their time slots must not overlap. Here, the time slots of request i and request j (i \neq j) overlap means that there exists a common integer in the closed intervals [L_i, R_i] and [L_j, R_j], that is, L_i \leq R_j and L_j \leq R_i both hold.

Find the maximum total profit of the approved requests (i.e., the maximum sum of V_i over all approved requests) when the selection of requests to approve is optimized. If no requests are approved, the total profit is 0 yen.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq T \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq T (1 \leq i \leq N)
• 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

3 5
1 3 5
2 4 6
4 5 3

Sample Output 1

8

Sample Input 2

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

Sample Output 2

7

Sample Input 3

10 20
1 5 10
3 7 15
6 10 12
8 12 8
11 15 20
1 3 7
4 6 9
7 9 11
10 14 14
15 20 18

Sample Output 3

59

Sample Input 4

20 50
1 5 100
3 8 150
6 10 120
9 15 200
12 18 180
16 20 90
19 25 160
22 28 140
26 30 110
29 35 170
32 38 130
36 40 190
1 3 80
4 7 95
8 11 105
14 17 115
21 24 85
30 34 145
37 42 175
43 50 250

Sample Output 4

1230

Sample Input 5

1 1
1 1 1000000000

Sample Output 5

1000000000

Problem Statement

Takahashi is in charge of analyzing weather data. His job is to examine temperature data from multiple observation stations and report stations with severe temperature fluctuations.

There are N observation stations. For each observation station i (1 \leq i \leq N), the daily average temperatures for the past M days, S_{i,1}, S_{i,2}, \ldots, S_{i,M}, are recorded.

Takahashi has decided to calculate a "temperature fluctuation score" for each observation station. The temperature fluctuation score for station i is defined as follows:

• Consider all possible ways to choose K consecutive days from the past M days of temperature data. For each interval of K consecutive days, find the difference between the maximum and minimum temperatures within that interval.
• The maximum of these differences is defined as the temperature fluctuation score of station i.

Takahashi needs to report the number of observation stations whose temperature fluctuation score is at least the threshold T.

Find the number of observation stations with a temperature fluctuation score of T or higher.

Constraints

• 1 \leq N \leq 500
• 1 \leq K \leq M \leq 10^5
• N \times M \leq 2 \times 10^6
• -10^9 \leq S_{i,j} \leq 10^9
• 0 \leq T \leq 2 \times 10^9
• All input values are integers.

Sample Input 1

3 5 3 5
1 3 4 8 2
10 11 12 13 14
0 -5 -1 -2 1

Sample Output 1

2

Sample Input 2

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

Sample Output 2

0

Sample Input 3

5 10 4 12
1 2 3 4 5 6 7 8 9 10
10 -5 8 7 6 5 4 3 2 1
-10 -8 -6 -4 -2 0 2 4 6 8
100 90 80 70 60 50 40 30 20 10
5 5 20 5 5 5 -10 5 5 5

Sample Output 3

3

Sample Input 4

8 15 5 20
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
30 25 20 15 10 5 0 -5 -10 -15 -20 -25 -30 -35 -40
-5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5
100 80 100 80 100 80 100 80 100 80 100 80 100 80 100
1 50 2 49 3 48 4 47 5 46 6 45 7 44 8
-100 -90 -80 -70 -60 -50 -40 -30 -20 -10 0 10 20 30 40
7 8 6 9 5 10 4 11 3 12 2 13 1 14 0
1000000000 999999990 999999980 999999970 999999960 -1000000000 -999999990 -999999980 -999999970 -999999960 0 10 20 30 40

Sample Output 4

5

Sample Input 5

1 1 1 0
-1000000000

Sample Output 5

1