Problem Statement

AtCoder Inc. sells merchandise through its online shop.

Takahashi has decided to purchase N types of products from there.
For each integer i from 1 to N, the i-th type of product has a price of P_i yen each, and he will buy Q_i of this.

Additionally, he must pay a shipping fee.
The shipping fee is 0 yen if the total price of the products purchased is S yen or above, and K yen otherwise.

He will pay the total price of the products purchased plus the shipping fee.
Calculate the amount he will pay.

Constraints

• 1\leq N\leq 100
• 1\leq S\leq 10000
• 1\leq K\leq 10000
• 1\leq P_i\leq 10000
• 1\leq Q_i\leq 100
• All input values are integers.

Sample Input 1

2 2000 500
1000 1
100 6

Sample Output 1

2100

Takahashi buys one product for 1000 yen and six products for 100 yen each.
Thus, the total price of the products is 1000\times 1+100\times 6=1600 yen.
Since the total amount for the products is less than 2000 yen, the shipping fee will be 500 yen.
Therefore, the amount Takahashi will pay is 1600+500=2100 yen.

Sample Input 2

3 2000 500
1000 1
100 6
5000 1

Sample Output 2

6600

The total price of the products is 1000\times 1+100\times 6+5000\times 1=6600 yen.
Since the total amount for the products is not less than 2000 yen, the shipping fee will be 0 yen.
Therefore, the amount Takahashi will pay is 6600+0=6600 yen.

Sample Input 3

2 2000 500
1000 1
1000 1

Sample Output 3

2000

There may be multiple products with the same price per item.

Problem Statement

AtCoder Inc. sells glasses and mugs.

Takahashi has a glass with a capacity of G milliliters and a mug with a capacity of M milliliters.
Here, G<M.

Initially, both the glass and the mug are empty.
After performing the following operation K times, determine how many milliliters of water are in the glass and the mug, respectively.

• When the glass is filled with water, that is, the glass contains exactly G milliliters of water, discard all the water from the glass.
• Otherwise, if the mug is empty, fill the mug with water.
• Otherwise, transfer water from the mug to the glass until the mug is empty or the glass is filled with water.

Constraints

• 1\leq K\leq 100
• 1\leq G<M\leq 1000
• G, M, and K are integers.

Sample Input 1

5 300 500

Sample Output 1

200 500

The operation will be performed as follows. Initially, both the glass and the mug are empty.

• Fill the mug with water. The glass has 0 milliliters, and the mug has 500 milliliters of water.
• Transfer water from the mug to the glass until the glass is filled. The glass has 300 milliliters, and the mug has 200 milliliters of water.
• Discard all the water from the glass. The glass has 0 milliliters, and the mug has 200 milliliters of water.
• Transfer water from the mug to the glass until the mug is empty. The glass has 200 milliliters, and the mug has 0 milliliters of water.
• Fill the mug with water. The glass has 200 milliliters, and the mug has 500 milliliters of water.

Thus, after five operations, the glass has 200 milliliters, and the mug has 500 milliliters of water. Hence, print 200 and 500 in this order, separated by a space.

Sample Input 2

5 100 200

Sample Output 2

0 0

Problem Statement

AtCoder Inc. sells T-shirts with its logo.

You are given Takahashi's schedule for N days as a string S of length N consisting of 0, 1, and 2.
Specifically, for an integer i satisfying 1\leq i\leq N,

• if the i-th character of S is 0, he has no plan scheduled for the i-th day;
• if the i-th character of S is 1, he plans to go out for a meal on the i-th day;
• if the i-th character of S is 2, he plans to attend a competitive programming event on the i-th day.

Takahashi has M plain T-shirts, all washed and ready to wear just before the first day.
In addition, to be able to satisfy the following conditions, he will buy several AtCoder logo T-shirts.

• On days he goes out for a meal, he will wear a plain or logo T-shirt.
• On days he attends a competitive programming event, he will wear a logo T-shirt.
• On days with no plans, he will not wear any T-shirts. Also, he will wash all T-shirts worn at that point. He can wear them again from the next day onwards.
• Once he wears a T-shirt, he cannot wear it again until he washes it.

Determine the minimum number of T-shirts he needs to buy to be able to wear appropriate T-shirts on all scheduled days during the N days. If he does not need to buy new T-shirts, print 0.
Assume that the purchased T-shirts are also washed and ready to use just before the first day.

Constraints

• 1\leq M\leq N\leq 1000
• S is a string of length N consisting of 0, 1, and 2.
• N and M are integers.

Sample Input 1

6 1
112022

Sample Output 1

2

If Takahashi buys two logo T-shirts, he can wear T-shirts as follows:

• On the first day, he wears a logo T-shirt to go out for a meal.
• On the second day, he wears a plain T-shirt to go out for a meal.
• On the third day, he wears a logo T-shirt to attend a competitive programming event.
• On the fourth day, he has no plans, so he washes all the worn T-shirts. This allows him to reuse the T-shirts worn on the first, second, and third days.
• On the fifth day, he wears a logo T-shirt to attend a competitive programming event.
• On the sixth day, he wears a logo T-shirt to attend a competitive programming event.

If he buys one or fewer logo T-shirts, he cannot use T-shirts to meet the conditions no matter what. Hence, print 2.

Sample Input 2

3 1
222

Sample Output 2

3

Sample Input 3

2 1
01

Sample Output 3

0

He does not need to buy new T-shirts.

Problem Statement

You are given two grids, A and B, each with H rows and W columns.

For each pair of integers (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W, let (i, j) denote the cell in the i-th row and j-th column. In grid A, cell (i, j) contains the integer A_{i, j}. In grid B, cell (i, j) contains the integer B_{i, j}.

You will repeat the following operation any number of times, possibly zero. In each operation, you perform one of the following:

• Choose an integer i satisfying 1 \leq i \leq H-1 and swap the i-th and (i+1)-th rows in grid A.
• Choose an integer i satisfying 1 \leq i \leq W-1 and swap the i-th and (i+1)-th columns in grid A.

Determine whether it is possible to make grid A identical to grid B by repeating the above operation. If it is possible, print the minimum number of operations required to do so.

Here, grid A is identical to grid B if and only if, for all pairs of integers (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W, the integer written in cell (i, j) of grid A is equal to the integer written in cell (i, j) of grid B.

Constraints

• All input values are integers.
• 2 \leq H, W \leq 5
• 1 \leq A_{i, j}, B_{i, j} \leq 10^9

Sample Input 1

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

Sample Output 1

3

Swapping the fourth and fifth columns of the initial grid A yields the following grid:

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

Then, swapping the second and third rows yields the following grid:

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

Finally, swapping the second and third columns yields the following grid, which is identical to grid B:

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

You can make grid A identical to grid B with the three operations above and cannot do so with fewer operations, so print 3.

Sample Input 2

2 2
1 1
1 1
1 1
1 1000000000

Sample Output 2

-1

There is no way to perform the operation to make grid A match grid B, so print -1.

Sample Input 3

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

Sample Output 3

0

Grid A is already identical to grid B at the beginning.

Sample Input 4

5 5
710511029 136397527 763027379 644706927 447672230
979861204 57882493 442931589 951053644 152300688
43971370 126515475 962139996 541282303 834022578
312523039 506696497 664922712 414720753 304621362
325269832 191410838 286751784 732741849 806602693
806602693 732741849 286751784 191410838 325269832
304621362 414720753 664922712 506696497 312523039
834022578 541282303 962139996 126515475 43971370
152300688 951053644 442931589 57882493 979861204
447672230 644706927 763027379 136397527 710511029

Sample Output 4

20

Problem Statement

AtCoder Inc. sells merchandise on its online shop.

There are N items remaining in the company. The weight of the i-th item (1\leq i\leq N) is W_i.

Takahashi will sell these items as D lucky bags.
He wants to minimize the variance of the total weights of the items in the lucky bags.
Here, the variance is defined as V=\frac{1}{D}\displaystyle\sum_{i=1}^D (x_i-\bar{x})^2, where x_1,x_2,\ldots,x_D are the total weights of the items in the lucky bags, and \bar{x}=\frac{1}{D}(x_1+x_2+\cdots+x_D) is the average of x_1,x_2,\ldots,x_D.

Find the variance of the total weights of the items in the lucky bags when the items are divided to minimize this value.
It is acceptable to have empty lucky bags (in which case the total weight of the items in that bag is defined as 0),
but each item must be in exactly one of the D lucky bags.

Constraints

• 2 \leq D\leq N\leq 15
• 1 \leq W_i\leq 10^8
• All input values are integers.

Sample Input 1

5 3
3 5 3 6 3

Sample Output 1

0.888888888888889

If you put the first and third items in the first lucky bag, the second and fifth items in the second lucky bag, and the fourth item in the third lucky bag, the total weight of the items in the bags are 6, 8, and 6, respectively.

Then, the average weight is \frac{1}{3}(6+8+6)=\frac{20}{3},
and the variance is \frac{1}{3}\left\{\left(6-\frac{20}{3}\right)^2+\left(8-\frac{20}{3}\right)^2+\left(6-\frac{20}{3}\right)^2 \right\}=\frac{8}{9}=0.888888\ldots, which is the minimum.

Note that multiple items may have the same weight, and that each item must be in one of the lucky bags.

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N) of length N.

We will perform the following operation on A for i = 1, 2, \ldots, M in this order.

• First, choose an integer between L_i and R_i, inclusive, uniformly at random and denote it as p.
• Then, change the value of A_p to the integer X_i.

For the final sequence A after the above procedure, print the expected value, modulo 998244353, of A_i for each i = 1, 2, \ldots, N.

Constraints

• All input values are integers.
• 1 \leq N, M \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• 1 \leq L_i \leq R_i \leq N
• 0 \leq X_i \leq 10^9

Sample Input 1

5 2
3 1 4 1 5
1 2 2
2 4 0

Sample Output 1

499122179 1 665496238 665496236 5

We start from the initial state A = (3, 1, 4, 1, 5) and perform the following two operations.

• The first operation chooses A_1 or A_2 uniformly at random, and changes its value to 2.
• Then, the second operation chooses one of A_2, A_3, A_4 uniformly at random, and changes its value to 0.

As a result, the expected values of the elements in the final A are (E_1, E_2, E_3, E_4, E_5) = (\frac{5}{2}, 1, \frac{8}{3}, \frac{2}{3}, 5).

Sample Input 2

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

Sample Output 2

5 6

Sample Input 3

20 20
998769066 273215338 827984962 78974225 994243956 791478211 891861897 680427073 993663022 219733184 570206440 43712322 66791680 164318676 209536492 137458233 289158777 461179891 612373851 330908158
12 18 769877494
9 13 689822685
6 13 180913148
2 16 525285434
2 14 98115570
14 17 622616620
8 12 476462455
13 17 872412050
14 15 564176146
7 13 143650548
2 5 180435257
4 10 82903366
1 2 643996562
8 10 262860196
10 14 624081934
11 13 581257775
9 19 381806138
3 12 427930466
6 19 18249485
14 19 682428942

Sample Output 3

821382814 987210378 819486592 142238362 447960587 678128197 687469071 405316549 318941070 457450677 426617745 712263899 939619994 228431878 307695685 196179692 241456697 12668393 685902422 330908158

Problem Statement

There are several balls. Each ball is one of the colors 1, 2, \ldots, N, and for each i = 1, 2, \ldots, N, there are A_i balls of color i.

Additionally, there are M boxes. For each j = 1, 2, \ldots, M, the j-th box can hold up to B_j balls in total.

Here, for all pairs of integers (i, j) satisfying 1 \leq i \leq N and 1 \leq j \leq M, the j-th box may hold at most (i \times j) balls of color i.

Print the maximum total number of balls that the M boxes can hold.

Constraints

• All input values are integers.
• 1 \leq N \leq 500
• 1 \leq M \leq 5 \times 10^5
• 0 \leq A_i, B_i \leq 10^{12}

Sample Input 1

2 3
8 10
4 3 8

Sample Output 1

14

You can do as follows to put a total of 14 balls into the boxes while satisfying the conditions in the problem statement.

• For balls of color 1, put one into the first box, one into the second box, and three into the third box.
• For balls of color 2, put two into the first box, two into the second box, and five into the third box.

Sample Input 2

1 1
1000000000000
0

Sample Output 2

0

Sample Input 3

10 12
59 168 130 414 187 236 330 422 31 407
495 218 351 105 351 414 198 230 345 297 489 212

Sample Output 3

2270