Problem Statement

Takahashi is a delivery planning manager at a shipping company. He needs to select exactly 1 truck out of N delivery trucks and assign it to a delivery task.

Each truck i (1 \leq i \leq N) has a fuel efficiency coefficient E_i. A truck with a larger fuel efficiency coefficient consumes more fuel to travel the same distance.

The delivery route consists of M segments, and the distance of the j-th segment (1 \leq j \leq M) is C_j. The selected truck will travel all M segments. The fuel consumed when truck i travels the j-th segment is E_i \times C_j.

The total fuel consumption when truck i is selected is

$\displaystyle \sum_{j=1}^{M} E_i \times C_j$

Find the minimum total fuel consumption when exactly 1 truck is chosen from the N trucks to minimize the total fuel consumption.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq E_i \leq 10^4 (1 \leq i \leq N)
• 1 \leq C_j \leq 10^4 (1 \leq j \leq M)
• All input values are integers
• The answer is at most 10^{13} and fits in a 64-bit integer

Sample Input 1

3 4
5 3 7
2 4 1 3

Sample Output 1

30

Sample Input 2

5 6
12 8 15 6 10
5 3 8 2 7 4

Sample Output 2

174

Sample Input 3

10 8
100 250 80 320 150 90 200 180 75 110
50 120 30 85 200 65 40 95

Sample Output 3

51375

Problem Statement

Takahashi works at the university's research support center. The university has N laboratories, and each laboratory is working on several research themes. Laboratory i (1 \leq i \leq N) is working on M_i research themes, each represented by a string of lowercase English letters W_{i,1}, W_{i,2}, \ldots, W_{i,M_i}. Note that the same research theme does not appear more than once within the same laboratory.

To promote collaborative research, the university has decided to investigate pairs of laboratories that are "eligible for collaboration." Let S_i = \{W_{i,1}, W_{i,2}, \ldots, W_{i,M_i}\} be the set of research themes that laboratory i is working on. Two laboratories i, j (i \neq j) are said to be "eligible for collaboration" if the number of research themes common to both S_i and S_j is at least K, that is, |S_i \cap S_j| \geq K holds. Here, whether two research themes are identical is determined by whether their representing strings match exactly.

Takahashi has the list of research themes each laboratory is working on. Based on this information, find the number of pairs of laboratories that are "eligible for collaboration." Note that the pair of laboratory i and laboratory j is considered the same as the pair of laboratory j and laboratory i. Count the number of pairs (i, j) satisfying 1 \leq i < j \leq N that meet the condition.

Constraints

• 2 \leq N \leq 500
• 1 \leq K \leq 50
• 1 \leq M_i \leq 50 (1 \leq i \leq N)
• W_{i,j} is a string of length between 1 and 20 consisting only of lowercase English letters (1 \leq i \leq N, 1 \leq j \leq M_i)
• The same research theme does not appear more than once within the same laboratory (that is, if j \neq k then W_{i,j} \neq W_{i,k})

Sample Input 1

3 2
3
ai ml data
4
ml data web security
2
ai ml

Sample Output 1

2

Sample Input 2

4 1
3
biology chemistry physics
2
chemistry medicine
4
physics math statistics chemistry
3
biology ecology environment

Sample Output 2

4

Sample Input 3

5 3
5
deeplearning nlp vision robotics optimization
4
nlp vision speech recognition
6
deeplearning nlp vision gan transformer diffusion
3
robotics control automation
5
nlp vision deeplearning bert attention

Sample Output 3

3

Problem Statement

Takahashi is hosting a quiz tournament in which N students participate.

Each student is assigned a student ID number from 1 to N, and student i has a quiz skill level of A_i.

At the start of the tournament, all N students remain, and "rounds" are repeated according to the following rules:

• Arrange the currently remaining students in ascending order of their student ID numbers, and divide them into groups of K from the front. That is, the 1st through K-th students in the arranged sequence form group 1, the (K{+}1)-th through 2K-th form group 2, and so on. If the last group has fewer than K students, it remains as a single group with that number of students.
• For each group, only the 1 student with the highest skill level in that group survives. If there are multiple students with the highest skill level, the one with the smallest student ID number among them survives. (If a group has only 1 student, that student survives as is.)
• If only 1 student remains, that student is declared the champion and the tournament ends. If 2 or more students remain, only the surviving students are kept and we return to step 1 to conduct the next round.

In each round, there are at least 2 remaining students, and since K \geq 2, at least one group contains 2 or more students, so the number of remaining students strictly decreases with each round. Therefore, the tournament ends after a finite number of rounds.

Determine the student ID number of the student who ultimately wins the tournament.

Constraints

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

Sample Input 1

6 2
3 1 4 1 5 9

Sample Output 1

6

Sample Input 2

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

Sample Output 2

10

Sample Input 3

15 4
12 5 9 3 15 7 11 2 8 14 1 6 13 10 4

Sample Output 3

5

Problem Statement

Takahashi and Aoki are each planning to post advertisements on an N \times N grid bulletin board. Each cell of the bulletin board is represented by coordinates (r, c) (1 \leq r \leq N, 1 \leq c \leq N), where r is the row number counted from the top and c is the column number counted from the left.

Takahashi plans to post A rectangular advertisements, and Aoki plans to post B rectangular advertisements on the bulletin board. Each advertisement covers a rectangular region specified by its top-left cell (r_1, c_1) and bottom-right cell (r_2, c_2). That is, all cells (r, c) satisfying r_1 \leq r \leq r_2 and c_1 \leq c \leq c_2 are covered.

The bulletin board manager is concerned that cells covered by both Takahashi's and Aoki's advertisements will look unsightly, and wants to know the total number of such overlapping cells in advance.

Find the number of cells that are covered by at least one of Takahashi's advertisements and also covered by at least one of Aoki's advertisements. Even if the same cell is covered by multiple combinations of advertisements, it is counted only once.

Constraints

• 1 \leq N \leq 500
• 1 \leq A \leq 100
• 1 \leq B \leq 100
• For each of Takahashi's advertisements i (1 \leq i \leq A): 1 \leq r_{1,i} \leq r_{2,i} \leq N, 1 \leq c_{1,i} \leq c_{2,i} \leq N
• For each of Aoki's advertisements j (1 \leq j \leq B): 1 \leq r_{1,j} \leq r_{2,j} \leq N, 1 \leq c_{1,j} \leq c_{2,j} \leq N
• All input values are integers

Sample Input 1

5 1 1
1 1 3 3
2 2 4 4

Sample Output 1

4

Sample Input 2

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

Sample Output 2

15

Sample Input 3

100 3 2
1 1 50 50
40 60 80 100
70 1 100 40
30 30 60 70
80 10 100 50

Sample Output 3

1323

Problem Statement

Takahashi is a programmer for delivery robots working in a large warehouse.

The warehouse floor is divided into an N \times N grid. The cell in the r-th row from the top (1 \leq r \leq N) and the c-th column from the left (1 \leq c \leq N) is assigned the number (r-1) \times N + c. That is, the cells are numbered 1, 2, \ldots, N from left to right in row 1, then N+1, N+2, \ldots, 2N from left to right in row 2, and so on. There are no walls or obstacles on the grid, and all cells are passable.

The delivery robot is currently waiting at cell S. Takahashi needs to move the robot to the shipping area at cell T. S and T are different cells. In one move, the robot can move one cell to an adjacent cell in one of the four directions (up, down, left, right). However, the robot cannot move outside the grid.

During its movement, the robot must collect packages from M designated shelves. The cell numbers P_1, P_2, \ldots, P_M where the shelves with packages to collect are located are given. These M cells may be visited in any order, but all of them must be visited at least once before reaching cell T. Note that passing through the same cell multiple times during movement is allowed.

Find the minimum number of moves required for the robot to start from cell S, visit all M designated cells, and reach cell T. Here, the number of moves refers to the total number of times the robot moves to an adjacent cell.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq M \leq 15
• 1 \leq S \leq N^2
• 1 \leq T \leq N^2
• 1 \leq P_i \leq N^2 (1 \leq i \leq M)
• P_i \neq P_j (i \neq j)
• S, T, P_1, P_2, \ldots, P_M are all distinct
• All input values are integers

Sample Input 1

3 2
1 9
5 3

Sample Output 1

6

Sample Input 2

5 0
1 25

Sample Output 2

8

Sample Input 3

100 5
1 10000
505 2550 7523 3001 9999

Sample Output 3

270