UTPC Contest 10-14-2026
A. Piece of Cake
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice has a giant cake for her birthday cut into $$$n$$$ slices. She isn't very good at cutting cake evenly, so each slice has size $$$s_i$$$.

She also has $$$m$$$ friends at her party, and each slice can be given to at most one friend without being split or combined with another slice. The $$$i$$$th friend is happy if they receive one slice of size at least $$$a_i$$$.

Alice wants to make as many friends happy as possible. Find the maximum number of friends Alice can make happy.

Input

The first line will contain integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 10^5)$$$.

The second line contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ $$$(1 \leq s_i \leq 10^9)$$$, the sizes of the slices.

The third line contains $$$m$$$ integers $$$a_1, a_2, \dots, a_m$$$ $$$(1 \leq a_j \leq 10^9)$$$, the minimum slice size each friend will accept.

Output

Print a single integer: the maximum number of friends who can be made happy.

Examples
Input
3 2
10 5 20
15 15
Output
1
Input
3 5
2 2 2
1 1 1 1 1
Output
3
Input
4 1
10 20 30 40
101
Output
0
Note

In the first example, only one slice has a size of at least $$$15$$$, so only one friend can be made happy.

In the second example, there are only three slices, so at most three friends can be made happy. Since every slice has size $$$2$$$ and every friend needs only $$$1$$$, three friends can be made happy.

In the third example, the largest slice has size $$$40$$$, which is less than the friend's requirement of $$$101$$$. Therefore, no friends can be made happy.

B. Lemon Tang (Korean Ver.)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Inspired by her group's new song, Stella decides to treat her friends to dessert! They have a lineup of $$$n$$$ lemon cheesecakes, where the $$$i$$$th one has sweetness $$$a_i$$$. All the members plan to share the cheesecakes, but unfortunately Jiwoo despises sour tastes.

Luckily Stella has $$$k$$$ spoonfuls of syrup, which she can apply to the cheesecakes as she wishes. For instance, she could choose to use all the syrup on a single cheesecake, or disperse such that each cake gets one spoon. Adding a spoon of syrup increases a cake's sweetness by $$$+1$$$. Jiwoo's score for the lineup is the smallest sweetness across all the cheesecakes.

Can you help Stella maximize Jiwoo's score?

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n,k \le 2 \cdot 10^5$$$), denoting the number of cheesecakes and the number of spoons of syrup.

The second line contains $$$n$$$ space-separated integers representing the array $$$a$$$, where $$$a_i$$$ denotes the sweetness of the $$$i$$$th cake ($$$1 \le a_i \le 10^9$$$).

Output

Output a single integer, denoting the maximum value for $$$\min_i a_i$$$ after using the syrup optimally.

Example
Input
4 5
3 1 4 2
Output
3
Note

In the sample, it is possible to transform $$$[3, 1, 4, 2]$$$ to $$$[4, 4, 4, 3]$$$, which gives a minimum value of $$$3$$$. It can be shown it is not possible to do better.

It may help to listen to the following song: https://open.spotify.com/track/0NGFAcYQVHCIdQea2qSs1I?si=fdd91b739c0c4549

C. Bake Sale
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The UTPC officers ordered too many Cabo Bob's burritos, and ran out of budget to buy food for the UT Open! In order to raise money, they decide to have a bake sale. But, being CS majors, none of them can cook, and they ran out of tokens to ask Claude for a recipe. They find a cookbook in the pantry, but realize that its author wrote the book for children, and thus scrambled the ingredients of every recipe in a word search. The officers have created a shopping list, but want to verify whether each ingredient is needed in the recipe so they don't overspend.

The recipe is printed as a grid of $$$r$$$ rows and $$$c$$$ columns of lowercase letters. An ingredient is hidden in the grid if you can trace its name through a sequence of cells where:

  • consecutive cells in the name share an edge (up, down, left, or right — no diagonals), and
  • no single cell is used more than once while tracing that one ingredient.

Unlike an ordinary word search, the path may bend: an ingredient can head one direction and then turn at any cell, snaking through the grid. Different ingredients are traced independently, so they may reuse the same cells.

For each ingredient on the shopping list, help the officers decide whether it is hidden in the grid.

Input

The first line contains two integers $$$r$$$ and $$$c$$$ ($$$1 \le r, c \le 10$$$) — the number of rows and columns in the grid.

Each of the next $$$r$$$ lines contains a string of exactly $$$c$$$ lowercase English letters, describing one row of the grid.

The next line contains a single integer $$$q$$$ ($$$1 \le q \le 50$$$) — the number of ingredients on the shopping list.

Each of the next $$$q$$$ lines contains one ingredient: a string of between $$$1$$$ and $$$10$$$ lowercase English letters.

Output

Print $$$q$$$ lines. On the $$$i$$$th line, print YES if the $$$i$$$th ingredient is hidden in the grid, and NO otherwise.

Examples
Input
5 5
sugar
bfyxx
ulour
txxxx
terxx
5
sugar
flour
butter
yeast
cream
Output
YES
YES
YES
NO
NO
Input
2 2
mi
kl
2
milk
oil
Output
YES
NO
Note

In the first example, sugar reads straight across the top row, while flour and butter bend as they are traced. yeast and cream cannot be formed.

In the second example, milk follows all four cells around the grid, while oil cannot be formed because there is no o.

D. EverythingIsCake
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

EverythingIsCake has always believed that everything is cake. Naturally, this means that when he decides to build something, he builds a cake.

EverythingIsCake has constructed a cake consisting of $$$n$$$ layers stacked from bottom to top. The width of the $$$i$$$-th layer is $$$a_i$$$.

EverythingIsCake considers the cake stable if every layer is no wider than the layer directly below it. In other words, the sequence of layer widths must be non-increasing, so

$$$a_1 \ge a_2 \ge \cdots \ge a_n$$$.

Unfortunately, his cake may not currently be stable.

To fix it, EverythingIsCake may eat one contiguous range of layers. After those layers are removed, the layers above them fall down while preserving their relative order. He may also choose to eat no layers if the cake is already stable.

Find the minimum number of consecutive layers EverythingIsCake must eat so that the remaining cake is stable.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$, the number of layers in EverythingIsCake's cake.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$, where $$$a_i$$$ is the width of the $$$i$$$-th layer, listed from bottom to top.

Output

Output a single integer, the minimum number of consecutive layers EverythingIsCake must eat so that the remaining cake is stable.

Examples
Input
6
8 6 3 7 5 2
Output
2
Input
5
9 9 7 4 1
Output
0
Note

In the first test case, the answer is $$$2$$$. EverythingIsCake can eat the two layers with widths $$$3$$$ and $$$7$$$, leaving the cake with layer widths

$$$8, 6, 5, 2$$$.

This sequence is non-increasing, so the cake is stable. It is impossible to make the cake stable by eating only one layer.

In the second test case, the cake is already stable since

$$$9 \ge 9 \ge 7 \ge 4 \ge 1$$$.

Therefore, EverythingIsCake does not need to eat any layers, so the answer is $$$0$$$.

E. The Great Karpish Bake Off
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Magikarp has entered the Karpish Bake Off with his magnum opus, Tres Peces, and the hungry judges expect it by time $$$T$$$.

To prepare his masterpiece, he has $$$n$$$ recipes, numbered $$$1,2,\ldots,n$$$, with recipe 1 being his Tres Peces. Recipe $$$i$$$ takes $$$t_i$$$ units of time and can begin only after its $$$m_i$$$ prerequisite recipes finish, while recipes without prerequisites can begin at time $$$0$$$.

The dependencies form a tree rooted at recipe $$$1$$$, meaning that every other recipe is a prerequisite of exactly one recipe and all recipes are needed for recipe $$$1$$$. Since Magikarp has unlimited KI (Karpificial Intelligence) agents, any number of recipes can be prepared in parallel.

Some of his recipes are also boostable. This means that Magikarp can choose one positive integer power level $$$x$$$ before cooking begins, which changes the duration of every boostable recipe to $$$$$$ \left\lfloor\frac{t_i}{x}\right\rfloor $$$$$$ units of time, while other recipes still take $$$t_i$$$ units of time.

Find the minimum power level such that Magikarp can finish his Tres Peces by time $$$T$$$, or determine that this is impossible.

Input

The first line contains two integers $$$n$$$ and $$$T$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$0\le T\le 10^{14}$$$) — the number of recipes and the deadline, respectively.

The second line contains $$$n$$$ integers $$$t_1,t_2,\ldots,t_n$$$ ($$$1\le t_i\le 10^9$$$) — the preparation times before boosting.

The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$b_i\in\{0,1\}$$$), where $$$b_i=1$$$ if recipe $$$i$$$ is boostable and $$$b_i=0$$$ otherwise.

The $$$i$$$th of the next $$$n$$$ lines contains an integer $$$m_i$$$ ($$$0\le m_i\le n-1$$$), followed by $$$m_i$$$ distinct integers $$$a_{i,1},a_{i,2},\ldots,a_{i,m_i}$$$ ($$$1\le a_{i,j}\le n$$$) — the number of prerequisite recipes and their recipe numbers, respectively.

Output

Output a single integer — the minimum positive integer power level such that Magikarp can finish his Tres Peces by time $$$T$$$, or -1 if this is impossible.

Examples
Input
3 6
3 8 5
0 1 1
2 2 3
0
0
Output
3
Input
2 3
4 10
0 1
1 2
0
Output
-1
Input
1 0
7
1
0
Output
8
Note

In the first example, recipes $$$2$$$ and $$$3$$$ are prepared in parallel before recipe $$$1$$$ begins. At power level $$$2$$$, recipe $$$1$$$ finishes at time $$$4+3=7$$$ and misses the deadline, whereas power level $$$3$$$ lets it finish at time $$$2+3=5$$$, so the answer is $$$3$$$.

In the second example, recipe $$$1$$$ alone takes $$$4$$$ units of time and cannot be boosted, so the deadline of $$$3$$$ is impossible.

In the third example, power level $$$8$$$ reduces the duration to $$$\lfloor\frac{7}{8}\rfloor=0$$$, while every smaller positive power level takes at least one unit of time.

F. Cake Mix-Up
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For his wedding, Mr. Nguyen ordered "a chocolate and vanilla cake" from the bakery, but whereas he expected to receive one chocolate cake and one vanilla cake, the bakery delivered him one massive wedding cake with mixed layers of chocolate and vanilla! Now, he wants to separate the layers of the wedding cake into two separate chocolate and vanilla cakes.

The cake sent by the bakery has $$$n$$$ cylindrical layers of decreasing radius from the bottom to the top, with interspersed chocolate and vanilla layers. In addition to the plate already occupied by the mixed-layer cake, denoted plate 1, Mr. Nguyen has two empty plates, denoted plates 2 and 3, on which he wants to construct the chocolate and vanilla cakes, respectively. In one second, Mr. Nguyen can transfer the top layer of a cake from one plate to a different plate. He does not want the cake to collapse, however, so he can only move layers onto layers of larger radius.

Mr. Nguyen needs your help to separate the chocolate and vanilla layers from the mixed-layer cake on plate 1 onto plates 2 and 3, respectively, in at most $$$2^n-1$$$ seconds.

Input

The first line of input contains $$$n$$$ ($$$2 \le n \le 20$$$), the number of total layers in the wedding cake.

The second line contains a bitstring $$$l$$$ of length $$$n$$$, listing the layers from bottom to top, where $$$l_i$$$ is 0 if layer $$$i$$$ is chocolate or 1 if it is vanilla. There is guaranteed to be at least one chocolate and one vanilla layer.

Output

The output should be at most $$$2^n-1$$$ lines consisting of a series of instructions in the form "$$$i$$$ $$$j$$$" ($$$1 \le i, j \le 3, i \ne j$$$), meaning a layer should be moved from plate $$$i$$$ to plate $$$j$$$. If the instructions are followed in order, plate 1 should be empty and plates 2 and 3 should contain the chocolate and vanilla cakes, respectively.

Example
Input
3
010
Output
1 2
1 3
2 3
1 2
3 2
Note

The diagram below illustrates the construction of the chocolate and vanilla cakes. This is done in 5 seconds, which is within the limit of $$$2^n-1=7$$$ seconds.

G. Layers Upon Layers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A peculiar chef is making a cake with several layers, with each layer having a flavor. He has already baked $$$n$$$ layers, each with a flavor $$$f_i.$$$

However, the chef believes the cake tastes best if the layers are arranged in a specific way: for each pair of adjacent layers, the last letter of the lower layer's flavor must be the same as the first letter of the flavor of the layer directly above it.

For example, listing the layers from the bottom up, the order apple, eggnog, gingerbread is valid. The order apple, dominos is not valid, since e is not the same as d. The order apple, extra, apple is valid.

In addition to arranging his layers, he can also do the following to at most one layer:

  • Flip the layer, which reverses the flavor's name. So, a layer with the flavor apple flipped would have the flavor elppa.

The chef wishes to use all $$$n$$$ of his layers exactly once. Given $$$f_1, f_2, \dots, f_n$$$, find if he is able to make a valid arrangement for his cake.

Input

The first line will contain $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, the number of layers the baker has.

Each of the next $$$n$$$ lines contains a string $$$f_i$$$ $$$(1 \leq |f_i| \leq 12)$$$, the flavor of the $$$i$$$-th layer, consisting only of lowercase Latin letters.

Output

If the chef cannot build a valid cake, print NO.

Otherwise, print YES followed by an integer $$$x$$$. Print $$$x=-1$$$ to flip no layer, or print the index $$$x$$$ ($$$1\le x\le n$$$) of the layer to flip.

If there are multiple valid answers, print any of them. Any $$$x$$$ is accepted as long as the chef can build a valid cake by flipping layer $$$x$$$ (or by flipping nothing, if $$$x = -1$$$).

Examples
Input
3
apple
eggnog
gingerbread
Output
YES -1
Input
3
ab
cb
cd
Output
YES 2
Input
2
cake
dough
Output
NO
Note

In the first example, no layer needs to be flipped: apple ends in e and eggnog starts with e, and eggnog ends in g and gingerbread starts with g.

In the second example, flipping layer $$$2$$$ turns cb into bc. Then ab, bc, cd is a valid cake. Without flipping, no valid cake exists.

In the third example, cake ends in e and dough ends in h, but the two flavors start with c and d. No arrangement works, even if either layer is flipped.

H. Lemon Tang (Japanese Ver.)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Lemon Tang was an absolute success! H2H has since released a Japanese version, and they are now preparing to perform in Japan to promote it (as well as their upcoming single!).

H2H is running choreo drills with their backup dancers, forming a line of $$$n$$$ people in total. Not everyone coaches the same way, though: the H2H members can keep an eye on a big chunk of the formation, while some backup dancers can only focus on the people right next to them. Dancer $$$i$$$ has a coaching radius of $$$r_i$$$.

They can run at most $$$k$$$ training sessions. A training session consists of picking a single dancer to lead, who then works with themselves and everyone within their coaching radius. Formally, if dancer $$$i$$$ leads a session, every dancer $$$j$$$ such that $$$|i-j| \le r_i$$$ has their dance score $$$d_j$$$ increase by $$$+1$$$. The same dancer may lead any number of sessions.

The performance will only be as strong as its weakest performer, i.e. the person with the smallest $$$d_j$$$. Can you help maximize this value?

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$): the number of dancers and the number of training sessions.

The second line contains $$$n$$$ space-separated integers $$$d_1, d_2, \ldots, d_n$$$ ($$$1 \le d_i \le 10^9$$$), where $$$d_i$$$ is the dance score of the $$$i$$$th dancer.

The third line contains $$$n$$$ space-separated integers $$$r_1, r_2, \ldots, r_n$$$ ($$$0 \le r_i \le n$$$), where $$$r_i$$$ is the coaching radius of the $$$i$$$th dancer.

Output

Output a single integer, denoting the maximum value of $$$\min_i d_i$$$ after assigning training sessions optimally.

Examples
Input
5 3
3 1 4 1 5
0 1 0 2 0
Output
3
Input
6 2
2 5 2 5 2 2
3 0 0 1 0 2
Output
3
Note

In the first sample, two sessions led by dancer $$$4$$$ achieve a minimum score of $$$3$$$: $$$$$$[3,1,4,1,5] \to [3,2,5,2,6] \to [3,3,6,3,7]$$$$$$

In the second sample, one session each led by dancers $$$1$$$ and $$$6$$$ achieves $$$3$$$. Reaching $$$4$$$ needs two sessions per endpoint, and no session covers both.

It may help to listen to the following song: https://open.spotify.com/track/7Duc0A2ye1eKwfCICOXYGT?si=f1e9ad0fd6e846cf