Problem Statement

Takahashi is the caretaker of an orchard. There are N fruit trees planted in this orchard, numbered 1, 2, \ldots, N. The height of fruit tree i is H_i.

Last night, a large typhoon passed through this area. Due to the typhoon's strong winds, fruit trees with height T or less had not yet developed sufficient roots and all fell over. That is, fruit tree i has fallen if and only if H_i \leq T.

To restore the orchard, Takahashi decided to replant all the fallen fruit trees. The cost to replant fruit tree i and restore it to its original state is C_i.

Find the total cost required to restore all fallen fruit trees to their original state.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq T \leq 10^9
• 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq C_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 3
1 5 3 4 2
10 20 30 40 50

Sample Output 1

90

Sample Input 2

4 2
5 10 8 3
100 200 300 400

Sample Output 2

0

Sample Input 3

10 50
10 20 30 40 50 60 70 80 90 100
5 15 25 35 45 55 65 75 85 95

Sample Output 3

125

Sample Input 4

20 500
100 200 300 400 500 600 700 800 900 1000 150 250 350 450 550 650 750 850 950 50
10 20 30 40 50 60 70 80 90 100 15 25 35 45 55 65 75 85 95 5

Sample Output 4

275

Sample Input 5

1 1000000000
1000000000
999999999

Sample Output 5

999999999

Problem Statement

Takahashi is in charge of quality control at a factory. Today, N products are coming along a conveyor belt.

Each product has a measured "internal temperature", and the internal temperature of the i-th product is W_i. A product whose internal temperature is at least the threshold T is a defective product. If a defective product is shipped as-is, a loss of D is incurred per product. Products with internal temperature less than T are not defective, so no loss is incurred when they are shipped.

Takahashi can select any number of products on the conveyor belt and apply "additional cooling treatment" to them. Each product can receive additional cooling treatment at most once, at a cost of C per product. If a defective product receives additional cooling treatment, it is no longer defective and can be shipped without incurring any loss. Additional cooling treatment can also be applied to non-defective products, but since those products would not have incurred any loss anyway, only the cost C is wasted.

All products will ultimately be shipped. Takahashi wants to minimize the sum of the total cost of additional cooling treatments and the total loss from shipping defective products that did not receive additional cooling treatment. Given that he can freely choose which products to apply additional cooling treatment to, find the minimum value of this sum.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq T \leq 10^9
• 1 \leq C \leq 10^9
• 1 \leq D \leq 10^9
• 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers.

Sample Input 1

5 30 10 25
15 30 25 40 35

Sample Output 1

30

Sample Input 2

7 50 100 40
60 30 55 45 80 50 10

Sample Output 2

160

Sample Input 3

10 1000000000 500000000 300000000
999999999 1000000000 500000000 1000000000 999999998 1000000000 200000000 1000000000 999999999 1000000000

Sample Output 3

1500000000

Problem Statement

Takahashi is in charge of forming a team to participate in a programming contest.

The club Takahashi belongs to has N members, and each member is identified by a number from 1 to N. Whether member i has contest experience is represented by the value H_i: H_i = 1 means experienced, and H_i = 0 means beginner. Additionally, member i's programming skill is represented by the value P_i.

Takahashi wants to select K members from the N members (without duplicates) to form a team for the contest. However, due to the contest rules, exactly M of the selected K members must be experienced, and exactly K - M must be beginners.

The team's overall strength is evaluated as the sum of the skill values P_i of the selected K members.

Find the maximum possible overall strength of the team when members are selected to satisfy the conditions. If no valid selection exists, output -1.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N
• 0 \leq M \leq K
• H_i \in \{0, 1\} (1 \leq i \leq N)
• 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5 3 1
1 100
0 80
0 90
1 50
0 70

Sample Output 1

270

Sample Input 2

6 4 2
1 500
0 300
1 400
0 600
1 200
0 350

Sample Output 2

1850

Sample Input 3

10 5 3
1 1000000000
0 999999999
1 800000000
0 750000000
1 600000000
0 500000000
1 400000000
0 300000000
0 200000000
0 100000000

Sample Output 3

4149999999

Problem Statement

Takahashi is trapped in a maze inside an old building.

The building is represented as a grid with N rows and M columns. The cell at the i-th row from the top and the j-th column from the left is called cell (i, j). The state of the i-th row of the grid is represented by the string S_i: if the j-th character of S_i is #, then cell (i, j) is a wall; if it is ., then cell (i, j) is a passage.

Takahashi is currently at cell (1, 1) and aims to reach the exit at cell (N, M) in the bottom-right corner.

In one operation, Takahashi can move from his current cell to one of the four adjacent cells (up, down, left, or right). However, he cannot move outside the grid. If the destination cell is a passage, he simply moves there. If the destination cell is a wall, he uses his hammer to destroy the wall, turning it into a passage, and then moves there. Each time a wall is destroyed, the destruction count increases by 1. A cell that has been destroyed and turned into a passage remains a passage thereafter. There is no limit on the number of times the hammer can be used, and there is no limit on the number of moves.

Since Takahashi can destroy walls as many times as needed, he can always reach cell (N, M). Find the minimum number of walls Takahashi needs to destroy to travel from cell (1, 1) to cell (N, M).

It is guaranteed that cell (1, 1) and cell (N, M) are always passages.

Constraints

• 1 \leq N \leq 500
• 1 \leq M \leq 500
• N, M are integers
• S_i (1 \leq i \leq N) is a string of length M consisting of # and .
• The 1st character of S_1 is .
• The M-th character of S_N is .

Sample Input 1

3 5
...#.
.###.
...#.

Sample Output 1

1

Sample Input 2

3 3
...
...
...

Sample Output 2

0

Sample Input 3

5 7
..#.#.#
.#...#.
##.#.##
.#...#.
..#.#..

Sample Output 3

2

Sample Input 4

10 10
..........
.########.
..........
.########.
..........
.########.
..........
.########.
..........
..........

Sample Output 4

0

Sample Input 5

1 1
.

Sample Output 5

0

Sample Input 6

3 5
...#.
.###.
...#.

Sample Output 6

1

Sample Input 7

3 3
...
...
...

Sample Output 7

0

Sample Input 8

5 7
.#.#.#.
.#.#.#.
.#.#.#.
.#.#.#.
.......

Sample Output 8

0

Sample Input 9

10 10
..........
.########.
..........
########.#
..........
.########.
..........
########.#
..........
..........

Sample Output 9

0

Sample Input 10

1 1
.

Sample Output 10

0

Problem Statement

Takahashi is attempting a stone jumping game to cross a river.

There are N stones lined up in a row in the river, numbered stone 1, stone 2, …, stone N from left to right. On stone i (1 \leq i \leq N), there are A_i coins placed.

Takahashi initially stands on stone 1. When Takahashi stands on a stone, he collects all the coins on that stone (including the coins on stone 1 where he starts). Coins on stones he does not visit cannot be collected. The number of coins is not necessarily positive; it can be negative, in which case he is forced to collect them as well.

While Takahashi has not yet reached stone N, he jumps to the right from his current stone. When he is currently on stone i (i < N), he can choose an integer d with 1 \leq d \leq K and move to stone i+d. However, the destination stone's number must be at most N. That is, he can jump to any one of stone i+1, stone i+2, \ldots, stone \min(i+K,\, N). Since movement is always to the right, he never stands on the same stone twice.

Takahashi must reach stone N. The game ends when he reaches stone N and collects its coins. Since K \geq 1 by the constraints, he can always reach stone N by advancing one step at a time from stone 1.

Find the maximum total number of coins Takahashi can collect starting from stone 1 and reaching stone N.

Constraints

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