Problem Statement

Takahashi enjoys mountain climbing as a hobby and is surveying the terrain of a certain mountain range.

This mountain range has N points arranged in a line, and the elevation of each point i (1 \leq i \leq N) is R_i. Takahashi wants to count how many "zigzag" portions exist in this sequence of elevations.

A "zigzag" is defined as follows. For three consecutive points i, i+1, i+2 (1 \leq i \leq N - 2), the triplet of points starting at point i is called a "zigzag" if it satisfies either of the following conditions:

• R_i < R_{i+1} and R_{i+1} > R_{i+2} (a pattern where elevation goes up then down)
• R_i > R_{i+1} and R_{i+1} < R_{i+2} (a pattern where elevation goes down then up)

In other words, a zigzag occurs when the elevation of the middle point is higher than both neighbors (peak type) or lower than both neighbors (valley type). If adjacent points have equal elevations, neither condition is satisfied, so it does not count as a zigzag.

Find the total number of zigzag triplets, that is, the number of values of i (1 \leq i \leq N - 2) that satisfy the above conditions.

Constraints

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

Sample Input 1

5
1 3 2 4 1

Sample Output 1

3

Sample Input 2

8
1 2 3 4 5 6 7 8

Sample Output 2

0

Sample Input 3

10
10 5 8 3 7 2 9 1 6 4

Sample Output 3

8

Problem Statement

Takahashi runs an orchard. The orchard has N fruit trees lined up in a row, numbered 1, 2, \ldots, N from left to right.

The i-th tree bears A_i fruits.

Due to a labor shortage this year, Takahashi cannot harvest all the trees, so he has decided to select exactly K consecutive trees to harvest. Specifically, he chooses an integer l (1 \leq l \leq N - K + 1) and harvests fruits from the K trees numbered l through l + K - 1. He must harvest all fruits from each of the K chosen trees (he cannot partially harvest a tree), and he does not harvest any fruits from the trees he did not choose.

Takahashi wants to minimize his workload, so he wants to minimize the total number of fruits harvested.

Find the minimum possible total number of fruits harvested when the K consecutive trees are chosen optimally.

Constraints

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

Sample Input 1

5 3
4 2 1 3 5

Sample Output 1

6

Sample Input 2

8 4
10 5 8 3 2 7 4 6

Sample Output 2

16

Sample Input 3

10 5
100 200 50 80 120 30 60 90 150 70

Sample Output 3

340

Problem Statement

Takahashi has come to a shopping mall. The mall sells N types of items, where the i-th item has a price of C_i yen and a satisfaction value of V_i for Takahashi.

Takahashi currently has S yen, but he must keep T yen as living expenses. In other words, the total amount spent on purchasing items must be at most S - T yen.

Each item can be purchased at most once. Find the maximum total satisfaction Takahashi can obtain.

Constraints

• 1 \leq N \leq 2000
• 1 \leq T \leq S \leq 10^5
• 1 \leq C_i \leq 10^5 (1 \leq i \leq N)
• 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers

Sample Input 1

3 100 30
30 50
40 60
50 80

Sample Output 1

110

Sample Input 2

3 50 50
10 100
20 200
30 300

Sample Output 2

0

Sample Input 3

8 500 100
100 200
150 300
200 500
80 150
120 250
250 600
50 100
180 400

Sample Output 3

900

Sample Input 4

15 10000 3000
500 1200
1200 3500
800 2000
1500 4000
300 700
2000 5500
700 1800
900 2400
1100 3000
600 1500
1800 4800
400 1000
1300 3600
250 600
950 2600

Sample Output 4

19200

Sample Input 5

1 1 1
1 1000000000

Sample Output 5

0

Problem Statement

Takahashi works part-time at a flower shop. Today he has been assigned the task of sorting N flowers into K bouquets.

Each flower i (1 \leq i \leq N) has an integer A_i representing its "stem length." All N flowers must be assigned to exactly one of the K bouquets. However, the number of flowers in each bouquet must be between 0 and M, inclusive. It is acceptable for a bouquet to contain no flowers at all.

If flowers in the same bouquet have a large difference in stem length, the bouquet will look unappealing. Therefore, Takahashi wants to sort the flowers so that the following condition is satisfied using a non-negative integer D:

• For every bouquet containing 2 or more flowers, the difference between the maximum and minimum stem lengths of the flowers in that bouquet is at most D.

For bouquets containing 0 or 1 flowers, this condition is automatically satisfied.

The smaller D is, the better each bouquet looks, but if D is too small, it may become impossible to sort all the flowers into K bouquets. On the other hand, if D is sufficiently large, only the capacity constraint of at most M flowers per bouquet needs to be considered, and since K \times M \geq N is guaranteed, it is always possible to sort the flowers.

Find the minimum value of D such that it is possible to assign all N flowers to K bouquets while satisfying the above condition. Since all A_i are integers, the answer is also a non-negative integer.

Constraints

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

Sample Input 1

5 2 3
1 3 5 8 10

Sample Output 1

4

Sample Input 2

4 2 2
1 5 10 20

Sample Output 2

10

Sample Input 3

10 3 4
2 5 8 11 15 20 25 30 33 37

Sample Output 3

10

Sample Input 4

20 5 5
3 7 12 18 25 31 38 42 50 55 63 70 78 85 90 96 100 108 115 120

Sample Output 4

20

Sample Input 5

1 1 1
1000000000

Sample Output 5

0

Problem Statement

Takahashi is walking through a city represented by a grid with H rows and W columns. Each cell of the grid is either a passable road (.) or a building (#). The coordinates of a cell are represented as (r, c) (row r, column c, both 1-indexed).

Takahashi's initial position is the cell marked @ on the grid. There are K lost kittens scattered around the city, and the cells where kittens are located are marked F on the grid. There is also exactly one animal shelter in the city, marked G on the grid. All of these cells (@, F, G) are passable, and no two of them occupy the same position.

Takahashi can move one step at a time from his current cell to an adjacent passable cell in one of the four cardinal directions (up, down, left, right). Diagonal movement and movement outside the grid are not allowed. He may pass through the same cell any number of times.

When Takahashi moves to a cell where a kitten is located, that kitten is automatically rescued and will travel with Takahashi from that point on. He cannot refuse to rescue a kitten when entering its cell, nor can he release a kitten once rescued. There are no restrictions on the order in which kittens are rescued. If he revisits a cell where a kitten has already been rescued, nothing happens.

Takahashi's goal is to be at the animal shelter cell with all lost kittens rescued. He may freely pass through the animal shelter cell along the way, but ultimately he must be at the animal shelter cell with all kittens rescued.

Find the minimum total number of steps required for Takahashi to start from his initial position, rescue all kittens, and reach the animal shelter. The number of steps at the start is 0. If it is impossible to rescue all kittens and reach the animal shelter, output -1.

Constraints

• 1 \leq H \leq 200
• 1 \leq W \leq 200
• 1 \leq K \leq 10
• There is exactly 1 @ in the grid
• There are exactly K Fs in the grid
• There is exactly 1 G in the grid
• S_i (1 \leq i \leq H) is a string of length W consisting only of ., #, @, F, G
• H, W, K are integers

Sample Input 1

3 5 2
@.F.G
.....
..F..

Sample Output 1

8

Sample Input 2

3 5 1
@.#F.
..#..
..#.G

Sample Output 2

-1

Sample Input 3

7 10 3
@........F
.########.
.#......#.
.#..F...#.
.#......#.
.########.
G........F

Sample Output 3

-1