MoBrook | 溪月阁

参加了Educational Codeforces Round 88 (Rated for Div. 2)，两个小时还是只A了两道题，一开始看错题把maximum看成minimum，第一题死活不过，第二题还好，20分钟左右，把第三题时间不够，遇到一些知识漏洞，记录一下。

A. Berland Poker

》英文原题《

Berland扑克一副牌n张,其中m张是joker。 一共k个玩家(n是k的倍数)。

一开始，每个玩家从牌堆抽n_k 张牌。谁的joker最多谁就是胜利者，并获得x−y分,x是胜利者手里的joker数,y是其他玩家手中joker的最大值。如果胜利者不止一个则不加分。

举亿些例子：

n=8, m=3, k=2。
其中第1个玩家拿到3张joker和1张普通牌，其他人拿到4张普通牌，则第1个玩家是胜利者，获得了3-0=3分;

n=4, m=2, k=4。
其中第1、2个玩家拿到1张普通牌，其他人拿到1张joker，因为同时有两个胜利者，所以没有人获得分数;

n=9, m=6, k=3。
其中第1个玩家拿到3张joker，第2个玩家拿到1张joker和2张普通牌，第3个玩家拿到2张joker和1张普通牌，则第1个玩家是胜利者，获得了3-2=1分;

n=42, m=0, k=7。
因为没有joker，所以每人都是胜利者，没有人获得分数;

Input

第一行是一个int t (1≤t≤500) — 输入test的数量，接着是t组test。

每个test包含3个int n, m, k (2≤n≤50, 0≤m≤n, 2≤k≤n，n是k的整数倍) — 扑克牌总数, joker数, 玩家数。

Output

输出t个test的结果，每个结果必须是一个int — 胜利者的分数的最大值

Example

input

4
8 3 2
4 2 4
9 6 3
42 0 7

output

3
0
1
0

Note

4组案例的情况在描述中提及了。

---

B. New Theatre Square

》英文原题《

有一个n行m列正方形组成的的区域，其中a_i,j表示第n行第m列的方块。

You are given the picture of the squares:

如果 a_i,j="*",则第n行第m列方块是黑色;
如果 a_i,j=".",则第n行第m列方块是白色。
你可以用下列瓷砖覆盖白色区域，但是不能覆盖黑色区域:

1×1 瓷砖 — 每个瓷砖需要花费 x 元，且只能覆盖 1×1 白色的区域;
1×2 瓷砖 — 每个瓷砖需要花费 y 元，且只能覆盖 1×2 白色的区域;
值得注意的是，你不能旋转1x2的瓷砖。

你需要在所有白色区域上面覆盖瓷砖，而不能在黑色区域上面覆盖瓷砖，且同一个区域不能覆盖两个瓷砖。

请你求出覆盖完所有区域需要花费的开销的最小值。

Input

第一行是一个int t (1≤t≤500) — 输入test的数量，接着是t组test。

每个test包含2行
第1行：
4个int n, m, x, y (1≤n≤100; 1≤m≤1000; 1≤x,y≤1000) — n行m列的区域，1x1瓷砖的价格，1x2瓷砖的价格。
第2行到第n+1行：
每行m个char。
如果是".",则是白色区域，
如果是"*",则是黑色区域。

保证每个test数据的 n x m 不大于105

Output

输出t个test的结果，每个结果必须是一个int — 覆盖所有白色区域的瓷砖的最小开销。

Example

input

4
1 1 10 1
.
1 2 10 1
..
2 1 10 1
.
.
3 3 3 7
..*
*..
.*.

output

10
1
20
18

Note

第1组案例的情况:
只能使用1x1瓷砖 10
最小开销：10

第2组案例的情况:
方案1 全部使用1x1瓷砖 20
方案2 尽可能多使用1x2瓷砖 1
最小开销：1

第3组案例的情况:
只能使用1x1瓷砖 20
最小开销：20

第4组案例的情况:
方案1 全部使用1x1瓷砖 18
方案2 尽可能多使用1x2瓷砖 20
最小开销：18

---

C. Mixing Water

》英文原题《

这里有两桶无限容量的水:
热水的温度是 h;
冷水的温度是 c (c<h)。

还有一个无限容量的空桶。

你需要按照下列次序进行操作:

先将一杯热水倒入桶中;
再将一杯热水倒入桶中;
再将已被热水...
以此类推。

需要注意的是你必须从热水开始倒，桶中水的温度等于倒入的水的温度的平均数。

你希望让桶中水的温度变成t。 如果此时桶中水的温度为t_b,|t_b−t|要尽可能小。

需要倒入多少杯水才能让桶中水的温度接近t

Input

第一行是一个int T (1≤T≤3⋅10⁴) — 输入test的数量，接着是t组test。

每个test包含3个int h, c, t (1≤c<h≤10⁶; c≤t≤h) — 热水的温度，冷水的温度，桶中水的目标温度。

Output

输出t个test的结果，每个结果必须是一个int — 需要倒入的水数量的最小值。

Example

input

3
30 10 20
41 15 30
18 13 18

output

2
7
1

Note

第1组案例的情况:
1热水
1冷水
（1x30+1x10）/(1+1) = 20
杯数：2

第2组案例的情况:
4热水
3冷水
（4x41+3x15）/(4+3) = 29.857
杯数：7

第3组案例的情况:
1热水
0冷水
（1x18+0x13）/(1+0) = 18
杯数：1

---

D. Yet Another Yet Another Task

》英文原题《

Alice 和 Bob 在玩 yet another 卡牌游戏。这个游戏的规则如下：
这里有n张卡放在同一行，第i张卡的值是a_i
首先，Alice 选择一段卡片，从第 l 张到第 r 张 (l≤r) 。然后 Bob 从这 Alice 选的段牌中移除第j张卡(l≤j≤r)。这局比赛的分数是 Alice 手中剩余的牌的值的和(a_l+a_l+1+⋯+a_j−1+a_j+1+⋯+a_r−1+a_r)。
特别的，如果 Alice 只选择了一张牌，在 Bob 移除之后，他将获得 0 分。

Alice 希望分数越高越好，Bob需要移除一张牌让 Alice 的分数尽可能的低。

Alice 需要如何取牌才能让分数尽可能大。输出分数的最大值。

Input

第一行是一个int n (1≤n≤10⁵) — 牌的数量。
第2行包含n个int a₁,a₂,...,a_n(-30≤a_i≤30) — 牌的值。

Output

输出1个int — 分数的最大值。

Examples

input`

5
5 -2 10 -1 4

output`

6

input2

8
5 2 5 3 -30 -30 6 9

output2

10

input3

3
-10 6 -15

output3

0

Note

第1组案例的情况:
Alice 选择 1~5
Bob 移除 3
分数：5+(−2)+(−1)+4=6

第2组案例的情况:
Alice 选择 1~4
Bob 移除 1或3
分数：5+2+3=10

第2组案例的情况:
Alice 选择 1~1或2~2或3~3
Bob 移除 1或2或3
如果 Alice 选择大于1张牌，结果将低于0
分数：0

---

E. Modular Stability

》英文原题《

---

F. RC Kaboom Show

》英文原题《