Problem Statement

Takahashi aims to become a weather forecaster and is practicing by forecasting the daily temperature at N locations.

Takahashi forecasted the temperature at each location over D days and recorded the results. Since he has just started practicing, his forecasted temperature for location i is the same value T_i degrees (Celsius) every day. On the other hand, the actual temperature at location i on day j was A_{i,j} degrees.

The "forecast error" for location i on day j is defined as the absolute difference between the forecasted temperature and the actual temperature, |A_{i,j} - T_i|.

To review the accuracy of his forecasts, Takahashi decided to find the sum of the forecast errors over the D days for each location. Specifically, for each location i (1 \leq i \leq N), he calculates the total forecast error:

S_i = \sum_{j=1}^{D} |A_{i,j} - T_i|

Find the maximum value among S_1, S_2, \ldots, S_N.

Constraints

• 1 \leq N \leq 10000
• 1 \leq D \leq 10000
• N \times D \leq 10^6
• -50 \leq T_i \leq 50 (1 \leq i \leq N)
• -50 \leq A_{i,j} \leq 50 (1 \leq i \leq N, 1 \leq j \leq D)
• All input values are integers.

Sample Input 1

3 4
10 0 -5
12 8 10 15
0 -3 4 1
-10 -5 0 -4

Sample Output 1

11

Sample Input 2

2 3
-2 7
-2 -1 -3
10 7 4

Sample Output 2

6

Sample Input 3

6 8
-10 0 15 20 -25 5
-10 -8 -12 0 10 -20 -30 -10
0 1 -1 2 -2 3 -3 4
15 15 16 14 30 0 -15 50
20 19 18 21 22 23 24 25
-50 -40 -30 -25 -20 -10 0 10
5 -5 15 -15 25 -25 35 -35

Sample Output 3

160

Sample Input 4

12 12
-50 -40 -30 -20 -10 0 10 20 30 40 50 5
-50 -49 -48 -47 -46 -45 -44 -43 -42 -41 -40 -39
-50 -45 -40 -35 -30 -25 -20 -15 -10 -5 0 5
-30 -30 -30 -30 -20 -10 0 10 20 30 40 50
-20 -25 -15 -30 -10 -35 -5 -40 0 -45 5 -50
-10 0 -20 10 -30 20 -40 30 -50 40 50 -10
0 0 0 0 0 0 0 0 0 0 0 0
10 9 8 7 6 5 4 3 2 1 0 -1
20 25 30 35 40 45 50 15 10 5 0 -5
30 20 10 0 -10 -20 -30 -40 -50 40 50 30
40 41 42 43 44 45 46 47 48 49 50 39
-50 -40 -30 -20 -10 0 10 20 30 40 50 50
5 -5 15 -15 25 -25 35 -35 45 -45 50 -50

Sample Output 4

550

Sample Input 5

1 1
-50
50

Sample Output 5

100

Problem Statement

Takahashi works part-time at a university library. At this library, the books a student can borrow are restricted based on their study level.

There are N students registered at the library, numbered from 1 to N. The study level of student i is an integer S_i.

The library has M books, numbered from 1 to M. The minimum study level required to borrow book j is an integer T_j.

Student i can borrow book j if and only if S_i \geq T_j.

Note that the same book can be borrowed by multiple students independently. That is, the number of books a student can borrow is not affected by the borrowing status of other students.

For each of the N students, determine the number of books that student can borrow. Specifically, for each i (1 \leq i \leq N), find the count C_i of books j (1 \leq j \leq M) satisfying S_i \geq T_j.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq T_j \leq 10^9 (1 \leq j \leq M)
• All inputs are integers

Sample Input 1

3 4
2 1 3
1 2 3 2

Sample Output 1

3
1
4

Sample Input 2

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

Sample Output 2

2
3
4
5
6

Sample Input 3

8 10
100 500 200 1000 300 50 750 400
150 300 500 100 250 600 800 450 200 350

Sample Output 3

1
8
3
10
5
0
9
6

Problem Statement

Takahashi is about to drive along a long highway. This highway has N toll gates lined up in a row, numbered from 1 to N, and each toll gate i is assigned an identification code consisting of a single lowercase alphabet letter. When the identification codes of the N toll gates are arranged in order of their numbers, a string S of length N is obtained. That is, the i-th character of S is the identification code of toll gate i.

Takahashi must pass through all toll gates from toll gate 1 to toll gate N in ascending order of their numbers. Normally, passing through each toll gate takes a travel time of 1, so without any optimization, the total travel time is N.

However, Takahashi has a discount pass. The discount pass is represented by a string T of length M. By using this discount pass, it may be possible to pass through exactly M consecutive toll gates together with a travel time of 1. The discount pass can be used any number of times, but the intervals to which it is applied must not overlap.

Specifically, the conditions for applying the discount pass are as follows. For an interval consisting of M consecutive toll gates, namely toll gates l, l+1, \ldots, l+M-1 (1 \leq l \leq N-M+1), if the string formed by arranging their identification codes in order (the substring of S from the l-th character to the (l+M-1)-th character) matches T, then the discount pass can be applied to that interval. When applied, those M toll gates can be passed together with a travel time of 1 (instead of the usual travel time of M).

Takahashi can choose 0 or more intervals to apply the discount pass, but no two chosen intervals may share a common toll gate. It is fine for the last toll gate of one interval and the first toll gate of another interval to have consecutive numbers (i.e., be adjacent).

Toll gates not included in any interval where the discount pass is applied are passed individually, each taking a travel time of 1. If the number of intervals where the discount pass is applied is k, the total travel time is k + (N - kM) = N - k(M - 1).

Find the minimum total travel time for Takahashi to pass through all toll gates.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq M \leq N
• N, M are integers
• S is a string of length N consisting of lowercase English letters
• T is a string of length M consisting of lowercase English letters

Sample Input 1

8 3
abcxxabc
abc

Sample Output 1

4

Sample Input 2

5 2
aaaaa
aa

Sample Output 2

3

Sample Input 3

30 4
abcaabcaabxabcayzabcaabcaqqqrr
abca

Sample Output 3

15

Sample Input 4

100 5
abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde
abcde

Sample Output 4

20

Sample Input 5

1 1
a
a

Sample Output 5

1

Problem Statement

Takahashi is participating in a rally that goes through N cities. The cities are numbered 1 through N.

This rally takes place over K days, from Day 1 to Day K. Takahashi stays in exactly one city each day. On Day 1, he can choose and stay in any of the N cities. From Day 2 onwards, he moves from the city he stayed in on the previous day to another city using a travel route, and stays there.

There are M travel routes available between cities, all of which are one-way. The k-th route represents travel from city a_k to city b_k. Using this route allows him to stay in city b_k on the day after he stayed in city a_k (travel in the reverse direction is not necessarily possible). It is guaranteed that a_k \neq b_k for each route.

From Day 2 onwards, he can only move to a city if there is a travel route starting from the city he stayed in on the previous day. Since there are no self-loops to the same city, he cannot stay in the same city for two consecutive days. However, he is allowed to stay in the same city again with other cities in between.

Each city i has a base score P_i. The score obtained by staying in city i on Day j (1 \leq j \leq K) is (P_i \times j) \bmod Q. Here, Q is a given positive integer, and \bmod denotes the non-negative remainder.

A staying plan for the K days is a sequence of city numbers of length K, c_1, c_2, \ldots, c_K, that satisfies all of the following conditions:

• Each c_j (1 \leq j \leq K) is an integer between 1 and N, inclusive (the same city number may appear multiple times in the sequence).
• For all 1 \leq j \leq K - 1, there exists a travel route from city c_j to city c_{j+1}.

Please maximize the total score over the K days, which is:

\sum_{j=1}^{K} \bigl((P_{c_j} \times j) \bmod Q\bigr)

Find the maximum value of this sum over all valid staying plans.

It is guaranteed that at least one valid staying plan exists.

Constraints

• 1 \leq N \leq 1000
• 0 \leq M \leq \min(N \times (N - 1),\; 50000)
• 1 \leq K \leq 1000
• 1 \leq Q \leq 10^6
• 0 \leq P_i \leq 10^6 (1 \leq i \leq N)
• 1 \leq a_k, b_k \leq N (1 \leq k \leq M)
• a_k \neq b_k (1 \leq k \leq M)
• There are no duplicate travel routes (i.e., all (a_k, b_k) are distinct).
• There is at least one valid staying plan.
• All input values are integers.

Sample Input 1

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

Sample Output 1

24

Sample Input 2

4 5 3 13
4 9 1 7
1 2
1 3
2 4
3 4
4 1

Sample Output 2

22

Sample Input 3

8 14 10 97
3 14 159 26 535 897 932 38
1 2
1 3
2 4
3 4
4 5
5 6
6 4
5 7
7 8
8 5
2 6
3 7
6 8
8 1

Sample Output 3

606

Sample Input 4

15 35 25 1000000
0 999999 123456 789012 345678 901234 567890 234567 890123 456789 111111 222222 333333 444444 555555
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 1
1 5
1 8
2 6
2 9
3 1
3 7
4 8
4 12
5 9
5 13
6 10
6 14
7 11
7 15
8 12
8 1
9 13
9 2
10 14
10 3

Sample Output 4

20223100

Sample Input 5

1 0 1 1
0

Sample Output 5

0

Problem Statement

There is a region consisting of N settlements. The road network of this region forms a tree structure, with settlement 1 as the root (central hub). Each settlement i (2 \leq i \leq N) has a parent settlement P_i, and settlement i and settlement P_i are directly connected by a road. There are N - 1 roads in total.

It has been decided to develop one waterway along each road. The construction of each waterway incurs a basic construction cost of 1. Furthermore, for each waterway construction, exactly one of the two settlements connected by the corresponding road must be chosen as the responsible settlement, and that settlement undertakes the construction. That is, for the waterway construction along the road connecting settlement i and settlement P_i, either settlement P_i or settlement i is chosen to be responsible. Every waterway must be assigned to one of the settlements.

Here, the waterways that each settlement i can be responsible for are only those corresponding to roads that have settlement i as an endpoint. Specifically, if settlement i is not the root, the eligible waterways are those for "the edge connecting settlement i and its parent P_i" and "the edges connecting settlement i and each of its child settlements." For settlement 1 (the root), which has no parent, only the waterways for edges to its child settlements are eligible.

For each settlement i (1 \leq i \leq N), a construction capacity C_i and an additional cost coefficient W_i are defined. Let m_i be the number of waterway constructions assigned to settlement i. If m_i is at most C_i, no additional cost is incurred. However, if m_i exceeds C_i, an additional cost of W_i is incurred for each excess waterway. That is, the additional cost incurred at settlement i is W_i \times \max(0,\, m_i - C_i).

The total cost is the sum of the basic construction costs of all waterways (always N - 1) plus the sum of additional costs incurred at all settlements:

\displaystyle (N - 1) + \sum_{i=1}^{N} W_i \times \max(0,\, m_i - C_i)

Determine the minimum total cost when the responsible settlement for each waterway is chosen optimally.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq i - 1 (2 \leq i \leq N)
• 0 \leq C_i \leq N (1 \leq i \leq N)
• 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

4
1 1 2
1 3
0 5
2 2
0 4

Sample Output 1

7

Sample Input 2

5
1 1 1 1
0 10
1 1
0 7
2 3
0 2

Sample Output 2

13

Sample Input 3

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

Sample Output 3

13

Sample Input 4

30
1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 10 10 11 12 13 14 15 16 17 18 20 24
1 100
3 5
0 20
2 7
1 12
3 4
0 50
1 9
2 6
0 30
4 2
1 15
0 11
2 8
1 25
0 3
2 18
1 10
3 1
0 40
1 13
2 5
0 17
1 22
3 6
0 14
2 9
1 16
0 19
4 2

Sample Output 4

115

Sample Input 5

2
1
0 1000000000
2 1

Sample Output 5

1