Problem Statement

Takahashi has obtained an old treasure map.

The map depicts a grid of N rows and M columns, and some cells are marked with signs indicating that treasure is buried there.

Takahashi wants to select a rectangular region that contains all cells where treasure is buried, and investigate the area within it. Here, a rectangular region is defined by a contiguous range of rows (from the r_1-th row to the r_2-th row from the top, where r_1 \leq r_2) and a contiguous range of columns (from the c_1-th column to the c_2-th column from the left, where c_1 \leq c_2), consisting of all cells that fall within both ranges. The number of cells contained in this region is (r_2 - r_1 + 1) \times (c_2 - c_1 + 1). A region consisting of just a single cell (when r_1 = r_2 and c_1 = c_2) is also considered a rectangular region.

To minimize the effort of investigation, Takahashi wants to find, among all rectangular regions that contain every cell where treasure is buried, the one with the minimum number of cells.

Find the minimum number of cells contained in a rectangular region that satisfies the condition.

Constraints

• 1 \leq N \leq 1000
• 1 \leq M \leq 1000
• N, M are integers
• S_i (1 \leq i \leq N) is a string of length M consisting of . and #, representing the state of the i-th row from the top of the map
• There is at least one # in total

Sample Input 1

3 4
....
.##.
.#..

Sample Output 1

4

Sample Input 2

5 6
......
.#....
......
....#.
......

Sample Output 2

12

Sample Input 3

8 10
..........
..#.......
..........
..........
.......#..
..........
..#.......
..........

Sample Output 3

36

Problem Statement

Takahashi is planning the placement of a sprinkler to be installed in a straight flower bed.

The flower bed stretches along a number line, and N shrubs are arranged on it from left to right. The i-th shrub is located at coordinate X_i and has P_i flowers planted in it. All shrubs are located at positive coordinates.

Takahashi has a water source at coordinate 0. From here, he will extend a pipe in the positive direction to supply water and install exactly one sprinkler at the end of the pipe. The sprinkler waters the area in the positive direction within a distance strictly less than D from its installation point. Note that the pipe only serves to deliver water to the sprinkler, and no watering occurs along the interval where the pipe passes.

Specifically, if the sprinkler is installed at coordinate s (where s is any non-negative real number), all flowers in the shrubs located at coordinates greater than or equal to s and less than s + D can be watered. That is, if the coordinate X_i of a shrub satisfies s \leq X_i < s + D, the P_i flowers in that shrub are considered watered. Flowers in shrubs that do not satisfy this condition cannot be watered.

Takahashi wants to minimize the number of flowers that cannot be watered by choosing the sprinkler installation position s optimally. Exactly one sprinkler must be installed.

Find the minimum number of flowers that cannot be watered.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq D \leq 10^9
• 1 \leq X_1 < X_2 < \cdots < X_N \leq 10^9
• 1 \leq P_i \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

10

Sample Input 2

4 3
2 10
5 20
6 5
9 15

Sample Output 2

25

Sample Input 3

12 10
1 4
4 8
9 3
13 20
18 7
21 15
27 6
31 12
36 5
42 18
48 9
55 11

Sample Output 3

76

Sample Input 4

25 50
3 12
17 40
28 7
44 25
61 33
79 18
95 50
123 9
146 21
170 60
199 14
225 32
260 45
288 11
319 27
347 36
380 8
415 55
451 19
490 24
530 42
575 13
621 31
670 48
725 16

Sample Output 4

591

Sample Input 5

1 1000000000
1000000000 1000000000

Sample Output 5

0

Problem Statement

Takahashi is participating in a "Shopping Marathon" held at a shopping street.

There are N shops lined up in a row from left to right in the shopping street. Each shop sells one type of product. The satisfaction of the product at the i-th shop from the left is A_i, and its price is B_i.

The rules of the Shopping Marathon are as follows. Takahashi must choose one contiguous interval from the shopping street and purchase exactly one product from every shop within that interval. Specifically, he chooses a pair of integers (l, r) (1 \leq l \leq r \leq N) and shops at every store from the l-th to the r-th from the left.

However, Takahashi's budget is limited, so the total price of the shops in the chosen interval B_l + B_{l+1} + \cdots + B_r must be at most K.

Takahashi wants to maximize the total satisfaction A_l + A_{l+1} + \cdots + A_r among all intervals satisfying this condition.

If no interval satisfies the condition (that is, if the price of every single shop exceeds K), Takahashi cannot purchase anything, and the total satisfaction is 0.

Find the maximum total satisfaction Takahashi can obtain.

Constraints

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

Sample Input 1

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

Sample Output 1

18

Sample Input 2

3 2
5 3
8 4
3 7

Sample Output 2

0

Sample Input 3

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

Sample Output 3

26

Sample Input 4

20 50
12 3
8 7
15 2
6 9
20 4
3 8
11 1
7 5
14 6
9 3
5 10
18 2
4 7
16 4
2 6
13 3
10 8
1 5
19 2
7 4

Sample Output 4

108

Sample Input 5

1 1000000000000
1000000000 1

Sample Output 5

1000000000

Problem Statement

Takahashi is planning to build flowerbeds in his garden. The garden consists of N plots arranged in a row, numbered 1, 2, \ldots, N from left to right. Each plot i has a "beauty" D_i and a "cost" C_i.

Takahashi will select some of these plots to plant flowers in. Each plot can either be chosen or not, and the same plot cannot be chosen multiple times. He may choose to select no plots at all. However, the following rules apply:

• The total budget for planting flowers is W. The sum of the costs of the chosen plots must be at most W.
• Planting flowers in adjacent plots generates a bonus due to unity. Specifically, consider partitioning the set of chosen plot numbers into maximal contiguous intervals. Here, a maximal contiguous interval is a subset of the set of chosen plot numbers whose elements are contiguous, and neither extending the left endpoint by subtracting 1 nor extending the right endpoint by adding 1 yields a plot number contained in the chosen set. For each maximal contiguous interval, let L be the number of plots contained in it:
• If L \geq 2, a bonus beauty of L \times B is obtained from that interval.
• If L = 1, an isolated plot alone does not create unity, so the bonus beauty is 0.

Here, B is a given non-negative integer constant. The total bonus beauty is the sum of the bonus beauty obtained from all maximal contiguous intervals. If no plots are chosen, there are no maximal contiguous intervals, and the bonus beauty is 0.

• For example, if plots \{2, 3, 4, 7, 8\} are chosen, the maximal contiguous intervals are \{2, 3, 4\} (length 3) and \{7, 8\} (length 2). The bonus beauty is 3 \times B + 2 \times B = 5B.
• For example, if plots \{3, 5\} are chosen, the maximal contiguous intervals are \{3\} (length 1) and \{5\} (length 1), and the bonus beauty is 0 + 0 = 0.

Takahashi wants to maximize (sum of beauty of chosen plots) + (total bonus beauty) such that the total cost of the chosen plots is at most W. If no plots are chosen, this value is 0.

Find this maximum value.

Constraints

• 1 \leq N \leq 2000
• 1 \leq W \leq 10000
• 0 \leq B \leq 10^6
• 1 \leq D_i \leq 10^6 (1 \leq i \leq N)
• 1 \leq C_i \leq W (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

24

Sample Input 2

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

Sample Output 2

20

Sample Input 3

12 25 7
15 4
8 3
20 6
5 2
13 5
18 7
9 3
25 8
6 2
14 4
11 5
22 6

Sample Output 3

121

Sample Input 4

25 100 50
120 8
75 5
210 14
95 7
160 11
40 3
185 13
130 9
55 4
240 16
105 8
90 6
170 12
65 5
200 15
110 7
45 3
155 10
220 17
80 6
145 9
60 4
190 13
100 7
250 18

Sample Output 4

2215

Sample Input 5

1 1 1000000
1000000 1

Sample Output 5

1000000

Problem Statement

Takahashi manages the floor of a warehouse divided into an N \times M grid. Each cell of the grid is either a wall (#) or a floor (.).

There are K robot vacuum cleaners placed on this floor. Each robot vacuum cleaner moves one cell up, down, left, or right every turn. The robot vacuum cleaners are programmed to operate according to the following rules:

• Each robot vacuum cleaner i is given a command sequence S_i of length L_i representing movement instructions. The command sequence consists of the characters U (up), D (down), L (left), and R (right).
• At turn t, robot vacuum cleaner i attempts to move one cell in the direction indicated by the ((t - 1) \bmod L_i) + 1-th character of its command sequence.
• If the destination is outside the grid or is a wall, the movement is ignored, and the robot vacuum cleaner stays in place for that turn.

Takahashi wants to know the position of each robot vacuum cleaner after T turns.

Given the initial position (R_i, C_i) (row R_i from the top, column C_i from the left) of robot vacuum cleaner i, its command sequence S_i, and the number of turns T, determine the position of each robot vacuum cleaner after T turns.

Note that multiple robot vacuum cleaners are allowed to occupy the same cell, and robot vacuum cleaners do not affect each other.

Constraints

• 1 \leq N \leq 2000
• 1 \leq M \leq 2000
• N M \leq 10^6
• 1 \leq K \leq 10^5
• 1 \leq T \leq 10^{18}
• g_i is a string of length M consisting of . or #
• 1 \leq R_i \leq N
• 1 \leq C_i \leq M
• The initial position (R_i, C_i) of robot vacuum cleaner i is a floor cell (.)
• 1 \leq L_i \leq 1000
• \displaystyle\sum_{i=1}^{K} L_i \leq 2 \times 10^5
• S_i is a string of length L_i consisting of U, D, L, R
• Let \mathcal{S} be the set of all distinct command sequences, and let A = \displaystyle\sum_{S \in \mathcal{S}} |S|. Then N M (A + K) \leq 2 \times 10^7 holds.
• All inputs are integers (N, M, K, T, R_i, C_i, L_i) and strings (g_i, S_i)

Sample Input 1

3 4 2 5
....
.#..
....
1 1 4 RRRD
3 4 3 ULL

Sample Output 1

2 4
1 2

Sample Input 2

2 3 3 4
.#.
...
1 1 1 R
1 3 2 DL
2 2 4 LRUD

Sample Output 2

1 1
2 1
2 2

Sample Input 3

8 10 6 123456789012
..........
.####..#..
.#....#...
.#.#..#.#.
...#......
##...###..
..#.......
.....#....
1 1 4 RDDR
3 4 6 URDLDR
5 10 3 LLL
8 1 8 UURRDDLL
6 3 5 DRRUL
2 7 4 DDLU

Sample Output 3

8 10
6 5
5 5
7 2
6 5
7 1

Sample Input 4

20 30 15 987654321987654321
..............................
.####.....######......####....
.#..#.....#....#......#..#....
.#..#.....#....#......#..#....
.####.....######......####....
..............................
.....#####..........#####.....
.....#..................#.....
.....#..##########..#...#.....
.....#..................#.....
.....#####..........#####.....
..............................
..########..####..########....
..#......#..#..#..#......#....
..########..####..########....
..............................
####....####....####....####..
..............................
..#..#..#..#..#..#..#..#..#...
..............................
1 1 4 RRRD
1 30 5 LLLDD
6 15 10 DDDRRRUUUL
8 10 12 RRRRDDLLLLUU
9 7 9 DRDRULULL
12 1 16 RRRRRRDDLLLLLLUU
13 1 7 RDRDRDL
14 15 6 UDLRRL
16 30 20 LLLLUUUURRRRDDDDLLLL
18 5 3 DDD
20 30 4 ULDR
7 1 8 RRRRRRRR
11 30 10 LLLLLDDUUU
19 1 5 RDRUR
4 29 11 LLUUURRRDDD

Sample Output 4

10 24
20 1
9 23
8 11
9 7
10 2
20 29
14 14
14 17
20 5
19 30
7 5
1 1
19 30
4 30

Sample Input 5

1 1 1 1000000000000000000
.
1 1 1 U

Sample Output 5

1 1