Problem Statement

Takahashi is trying to choose books to reread while organizing his bookshelf.

There are N books on the bookshelf, and for the i-th book (1 \leq i \leq N), a value C_i representing "the number of times it has been read so far" and a value D_i representing "satisfaction" are recorded.

Takahashi decided to prioritize rereading books that he has read fewer times. Specifically, he wants to select all books that have been read K times or fewer as candidates for rereading, and he wants to know the total satisfaction of those books.

From the N books, find the total satisfaction of all books that have been read K times or fewer. If there are no such books, the total is 0.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq 10^9
• 0 \leq C_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers
• It is guaranteed that the answer is at most 2 \times 10^{14}

Sample Input 1

5 2
1 10
3 20
0 15
2 30
5 25

Sample Output 1

55

Sample Input 2

4 1
5 100
3 200
10 50
2 300

Sample Output 2

0

Sample Input 3

10 5
3 120
7 250
5 80
0 300
12 60
4 150
6 90
1 200
9 110
5 170

Sample Output 3

1020

Sample Input 4

20 100
50 1000000000
101 500000000
99 800000000
200 300000000
0 999999999
100 750000000
150 600000000
30 450000000
75 200000000
110 350000000
1 900000000
88 100000000
100 550000000
250 400000000
99 650000000
1000000000 1000000000
45 700000000
102 850000000
100 500000000
60 300000000

Sample Output 4

7899999999

Sample Input 5

1 0
0 1

Sample Output 5

1

Problem Statement

Takahashi works as a street light manager at the city hall. The street he is responsible for has N street lights arranged in a row, numbered 1, 2, \ldots, N from left to right.

Each street light i is given an integer value A_i representing its initial brightness. When Takahashi performs maintenance on street light i, the effect extends not only to that street light but also to its adjacent street lights. Specifically, the brightness of all street lights among i-1, i, i+1 whose numbers are between 1 and N (inclusive) increases by 1.

Takahashi performs a total of M maintenance operations. In the j-th operation (1 \leq j \leq M), he performs maintenance on street light B_j. Note that the same street light may be maintained multiple times.

Determine the brightness of each street light after all operations are completed.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• 1 \leq B_j \leq N
• All input values are integers

Sample Input 1

5 3
1 2 3 4 5
2 4 4

Sample Output 1

2 3 6 6 7

Sample Input 2

7 5
0 0 0 0 0 0 0
1 3 5 7 4

Sample Output 2

1 2 2 3 2 2 1

Sample Input 3

10 8
100 200 300 400 500 600 700 800 900 1000
1 1 5 5 5 10 3 7

Sample Output 3

102 203 301 404 503 604 701 801 901 1001

Problem Statement

Takahashi is in charge of managing the school's flower bed. The flower bed has N plots arranged in a row, and the i-th plot from the left (1 \leq i \leq N) has a flower of color C_i planted in it. Here, flower colors are represented by positive integers.

Aoki asked Takahashi Q questions to investigate the appearance of the flower bed. In the flower bed, if two adjacent plots have flowers of the same color, there is little visual variation and it looks monotonous. Therefore, Aoki wants to know how many places within a specified range have adjacent plots with the same flower color.

In the j-th question (1 \leq j \leq Q), a range from plot L_j to plot R_j is specified. Find the number of integers i satisfying L_j \leq i \leq R_j - 1 and C_i = C_{i+1}. In other words, among the pairs of adjacent plots within the contiguous interval from plot L_j to plot R_j, count the number of pairs where the flower colors match.

Find the answer for each of the Q questions.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq L_j < R_j \leq N (1 \leq j \leq Q)
• All input values are integers.

Sample Input 1

5 3
1 1 2 2 2
1 5
1 3
3 5

Sample Output 1

3
1
2

Sample Input 2

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

Sample Output 2

4
1
2
2
1

Sample Input 3

15 8
10 10 5 5 5 3 3 7 7 7 7 1 1 2 2
1 15
1 5
5 10
10 15
3 7
2 14
6 8
1 2

Sample Output 3

9
3
3
3
3
7
1
1

Problem Statement

Takahashi is in charge of forming a project team at his company.

There are N employees in the company, each assigned an employee number from 1 to N. The ability value of employee i is A_i.

Takahashi has decided to select exactly K employees from the N employees to form a team. The same employee cannot be selected more than once, and each employee is either selected for the team or not.

However, there may be compatibility issues between some employees. M "incompatible pairs" are given, where the j-th pair consists of employee U_j and employee V_j. If both of these employees are selected for the team, their coordination suffers and the team's overall strength decreases by B_j. If only one of the pair is selected, or neither is selected, no decrease occurs.

Specifically, let S (S \subseteq \{1, 2, \ldots, N\}, |S| = K) be the set of employee numbers of the K selected employees. The team's overall strength is defined as follows:

\sum_{i \in S} A_i \ - \sum_{\substack{1 \leq j \leq M \\ U_j \in S \text{ and } V_j \in S}} B_j

That is, it is the total ability values of the K selected employees minus the total decrease from all incompatible pairs where both members are included in S.

When Takahashi selects K employees to maximize the team's overall strength, find the maximum value of the team's overall strength. Note that the overall strength may be negative, but even in that case, output the maximum value as is.

Constraints

• 1 \leq N \leq 18
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq K \leq N
• 1 \leq A_i \leq 10^9
• 1 \leq U_j < V_j \leq N
• 1 \leq B_j \leq 10^9
• All (U_j, V_j) are distinct
• All input values are integers

Sample Input 1

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

Sample Output 1

16

Sample Input 2

5 4 3
100 90 80 70 60
1 2 50
1 3 40
2 3 30
4 5 10

Sample Output 2

220

Sample Input 3

8 6 4
1000000000 900000000 800000000 700000000 600000000 500000000 400000000 300000000
1 2 500000000
1 3 400000000
2 3 300000000
1 4 200000000
5 6 100000000
7 8 50000000

Sample Output 3

2700000000

Problem Statement

Takahashi works as a delivery driver. There are a total of N locations relevant to today's deliveries, each numbered from 1 to N. Location 1 is the distribution center (serving as both the starting point and the return point), and locations 2 through N are the destinations where packages must be delivered.

Each location i is positioned at coordinates (X_i, Y_i) on a two-dimensional plane. Note that different locations may share the same coordinates.

Takahashi plans a tour route starting from the distribution center (location 1), visiting all destinations (locations 2 through N) exactly once each, and then returning to the distribution center (location 1). Specifically, he chooses a permutation (p_1, p_2, \ldots, p_{N-1}) of (2, 3, \ldots, N) and travels in the order:

1 \to p_1 \to p_2 \to \cdots \to p_{N-1} \to 1

The fuel cost for Takahashi's delivery truck to travel directly from coordinates (a, b) to coordinates (c, d) is calculated as (a - c)^2 + (b - d)^2.

The total fuel cost of the tour route is the sum of the travel costs between each pair of consecutive locations along the route. Specifically, the fuel cost of the above tour route is:

\mathrm{dist}(1, p_1) + \sum_{k=1}^{N-2} \mathrm{dist}(p_k, p_{k+1}) + \mathrm{dist}(p_{N-1}, 1)

where \mathrm{dist}(i, j) = (X_i - X_j)^2 + (Y_i - Y_j)^2 represents the travel cost from location i to location j.

Takahashi wants to minimize the total fuel cost of the tour route by freely choosing the order in which he visits the destinations. Travel is done directly along the tour route; he cannot pass through other locations or arbitrary coordinates along the way.

Find the minimum fuel cost.

Constraints

• 2 \leq N \leq 16
• -1000 \leq X_i \leq 1000 \quad (1 \leq i \leq N)
• -1000 \leq Y_i \leq 1000 \quad (1 \leq i \leq N)
• All input values are integers

Sample Input 1

2
0 0
1 1

Sample Output 1

4

Sample Input 2

4
0 0
1 0
1 1
0 1

Sample Output 2

4

Sample Input 3

5
0 0
3 0
3 4
-1 3
0 3

Sample Output 3

46