Problem Statement

Takahashi is managing a reservation system for concert tickets of a popular artist.

The concert venue has N types of seating areas, numbered from 1 to N. Each area i (1 \leq i \leq N) has a ticket price C_i and a capacity (number of seats) K_i.

M fans, from the 1-st to the M-th, attempt to reserve tickets one at a time in order. The j-th fan tries to reserve a ticket for area P_j. If the number of reservations already made for area P_j at that point is less than the capacity K_{P_j}, the fan successfully reserves a ticket for area P_j, and the number of reservations for area P_j increases by 1. If the number of reservations already equals the capacity K_{P_j}, the fan cannot make a reservation. A fan who fails to reserve does not attempt to reserve in any other area.

After all fans have been processed, find the total ticket price of the fans who successfully reserved tickets. The ticket price for a fan who reserved a ticket in area i is C_i.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq C_i \leq 10^4 (1 \leq i \leq N)
• 1 \leq K_i \leq 10^5 (1 \leq i \leq N)
• 1 \leq P_j \leq N (1 \leq j \leq M)
• All input values are integers

Sample Input 1

2 5
500 2
1000 1
1
1
1
2
2

Sample Output 1

2000

Sample Input 2

3 8
300 3
700 2
1500 1
1
2
3
1
2
1
3
2

Sample Output 2

3800

Sample Input 3

5 12
1000 2
2500 3
800 1
5000 2
1200 4
1
2
3
4
5
1
2
2
3
4
5
5

Sample Output 3

23900

Problem Statement

Takahashi is conducting an experiment rolling balls on M squares arranged in a row.

The squares are numbered from 1 to M, where square 1 is at the highest position and square M is at the lowest position. There is a step between each pair of adjacent squares, and the step between square i (1 \leq i \leq M - 1) and square i + 1 has a weight threshold W_i that determines whether a ball can pass through. A ball with weight at least W_i can roll over this step to square i+1, but a ball with weight less than W_i cannot pass this step and stops there.

Takahashi conducts the experiment using N balls. Ball j (1 \leq j \leq N) has weight B_j. For each ball, the following experiment is performed independently of the other balls.

When Takahashi places ball j on square 1, the ball rolls according to the following rules:

1. Let p be the current square of the ball. Initially, p = 1.
2. If p < M and B_j \geq W_p, the ball rolls to square p + 1 (update p to p + 1). This step is repeated as long as the condition is satisfied.
3. If p = M or B_j < W_p, the ball stops at square p.

For each ball, determine the number of the square where it finally stops.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 2 \times 10^5
• 1 \leq W_i \leq 10^9 (1 \leq i \leq M - 1)
• 1 \leq B_j \leq 10^9 (1 \leq j \leq N)
• All input values are integers

Sample Input 1

3 5
2 5 3 1
4 1 10

Sample Output 1

2
1
5

Sample Input 2

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

Sample Output 2

1
1
6
6
6

Sample Input 3

7 10
5 12 8 20 3 15 6 10 25
10 20 5 30 1 8 100

Sample Output 3

2
9
2
10
1
2
10

Problem Statement

In Mr. Aoki's class, N students took a test. Each student is assigned a student ID number from 1 to N, and student i scored A_i points.

Mr. Aoki is considering pairing up two different students for group work. As a measure of a pair's ability, he defines the "pair score" as the sum of the two students' scores.

Mr. Aoki wants to know how many pairs have a pair score of at least a certain threshold K.

Among all pairs of distinct students (i, j) (1 \leq i < j \leq N), find the number of pairs satisfying A_i + A_j \geq K.

Constraints

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

Sample Input 1

4 6
1 3 5 7

Sample Output 1

5

Sample Input 2

3 10
1 2 3

Sample Output 2

0

Sample Input 3

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

Sample Output 3

9

Sample Input 4

15 100
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50

Sample Output 4

105

Sample Input 5

2 2000000000
1000000000 1000000000

Sample Output 5

1

Problem Statement

As a guild master, Takahashi must form a party of adventurers to challenge a dungeon.

The guild has N adventurers. Each adventurer i (1 \leq i \leq N) has an attack power A_i and a defense power B_i.

Takahashi will select exactly K adventurers from the N adventurers to form a party. The same adventurer cannot be selected more than once. The party's combat power is calculated according to the following rules:

• Let S be the sum of the attack powers of the K selected adventurers.
• Let M be the minimum defense power among the K selected adventurers.
• The party's combat power is S \times M.

No matter how high the total attack power of the party is, if the minimum defense power is small, the party's combat power will suffer.

Find the maximum possible combat power of the party when the selection of K adventurers is chosen optimally.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^6
• 1 \leq B_i \leq 10^6
• All inputs are integers.

Sample Input 1

4 2
3 5
8 2
6 4
5 3

Sample Output 1

36

Sample Input 2

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

Sample Output 2

40

Sample Input 3

8 3
5 9
12 4
7 8
10 6
3 11
9 5
6 10
8 7

Sample Output 3

150

Sample Input 4

15 7
13 9
21 4
8 15
17 11
5 20
19 7
14 10
6 18
25 3
11 14
9 16
16 8
7 19
18 12
10 13

Sample Output 4

880

Sample Input 5

1 1
1000000 1000000

Sample Output 5

1000000000000

Problem Statement

Takahashi is a surveyor for urban planning. Along a straight street, N buildings stand in a row. They are numbered Building 1, Building 2, ..., Building N from left to right, and the height of Building i is H_i. All building heights are distinct.

For each Building i (1 \leq i \leq N), we define a "view score" as follows.

First, among the buildings to the right of Building i (those with numbers greater than i) that are taller than Building i, let Building R_i be the nearest one. That is, R_i is the smallest j > i such that H_j > H_i. If no such building exists, then R_i does not exist.

Similarly, among the buildings to the left of Building i (those with numbers less than i) that are taller than Building i, let Building L_i be the nearest one. That is, L_i is the largest j < i such that H_j > H_i. If no such building exists, then L_i does not exist.

Intuitively, the view score of Building i is the number of buildings in the contiguous interval containing Building i that extends left and right until reaching a taller building (or the end of the street) in each direction. Specifically, it is determined as follows:

• If both L_i and R_i exist: the score is R_i - L_i - 1 (the number of buildings between Building L_i and Building R_i)
• If only R_i exists and L_i does not exist: the score is R_i - 1 (the number of buildings from Building 1 to Building R_i - 1)
• If only L_i exists and R_i does not exist: the score is N - L_i (the number of buildings from Building L_i + 1 to Building N)
• If neither exists: the score is N (the total number of buildings)

Takahashi needs to answer Q questions. For each question, an integer X_k is given. Answer the number of buildings whose view score is at least X_k.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
• All H_i are distinct
• 1 \leq X_k \leq N (1 \leq k \leq Q)
• All input values are integers

Sample Input 1

5 4
3 1 4 2 5
1
2
3
5

Sample Output 1

5
3
2
1

Sample Input 2

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

Sample Output 2

7
3
2
1

Sample Input 3

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

Sample Output 3

10
6
4
2
1

Sample Input 4

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

Sample Output 4

15
8
4
1
1
1

Sample Input 5

1 1
1000000000
1

Sample Output 5

1