apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Little boy Petya loves stairs very much. But he is bored from simple going up and down them — he loves jumping over several stairs at a time. As he stands on some stair, he can either jump to the next one or jump over one or two stairs at a time. But some stairs are too dirty and Petya doesn't want to step on them.

Now Petya is on the first stair of the staircase, consisting of n stairs. He also knows the numbers of the dirty stairs of this staircase. Help Petya find out if he can jump through the entire staircase and reach the last stair number n without touching a dirty stair once.

One has to note that anyway Petya should step on the first and last stairs, so if the first or the last stair is dirty, then Petya cannot choose a path with clean steps only.

## Input Format
The first line contains two integers n and m (1 ≤ n ≤ 109, 0 ≤ m ≤ 3000) — the number of stairs in the staircase and the number of dirty stairs, correspondingly. The second line contains m different space-separated integers d1, d2, ..., dm (1 ≤ di ≤ n) — the numbers of the dirty stairs (in an arbitrary order).

## Output Format
Print "YES" if Petya can reach stair number n, stepping only on the clean stairs. Otherwise print "NO".

## Examples
```input
10 5
2 4 8 3 6
```
```output
NO
```
-----
```input
10 5
2 4 5 7 9
```
```output
YES
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Petya is a beginner programmer. He has already mastered the basics of the C++ language and moved on to learning algorithms. The first algorithm he encountered was insertion sort. Petya has already written the code that implements this algorithm and sorts the given integer zero-indexed array a of size n in the non-decreasing order.

Petya uses this algorithm only for sorting of arrays that are permutations of numbers from 0 to n - 1. He has already chosen the permutation he wants to sort but he first decided to swap some two of its elements. Petya wants to choose these elements in such a way that the number of times the sorting executes function swap, was minimum. Help Petya find out the number of ways in which he can make the swap and fulfill this requirement.

It is guaranteed that it's always possible to swap two elements of the input permutation in such a way that the number of swap function calls decreases.

## Input Format
The first line contains a single integer n (2 ≤ n ≤ 5000) — the length of the permutation. The second line contains n different integers from 0 to n - 1, inclusive — the actual permutation.

## Output Format
Print two integers: the minimum number of times the swap function is executed and the number of such pairs (i, j) that swapping the elements of the input permutation with indexes i and j leads to the minimum number of the executions.

## Examples
```input
5
4 0 3 1 2
```
```output
3 2
```
-----
```input
5
1 2 3 4 0
```
```output
3 4
```

## Note
In the first sample the appropriate pairs are (0, 3) and (0, 4).

In the second sample the appropriate pairs are (0, 4), (1, 4), (2, 4) and (3, 4).

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A little boy Petya dreams of growing up and becoming the Head Berland Plumber. He is thinking of the problems he will have to solve in the future. Unfortunately, Petya is too inexperienced, so you are about to solve one of such problems for Petya, the one he's the most interested in.

The Berland capital has n water tanks numbered from 1 to n. These tanks are connected by unidirectional pipes in some manner. Any pair of water tanks is connected by at most one pipe in each direction. Each pipe has a strictly positive integer width. Width determines the number of liters of water per a unit of time this pipe can transport. The water goes to the city from the main water tank (its number is 1). The water must go through some pipe path and get to the sewer tank with cleaning system (its number is n).

Petya wants to increase the width of some subset of pipes by at most k units in total so that the width of each pipe remains integer. Help him determine the maximum amount of water that can be transmitted per a unit of time from the main tank to the sewer tank after such operation is completed.

## Input Format
The first line contains two space-separated integers n and k (2 ≤ n ≤ 50, 0 ≤ k ≤ 1000). Then follow n lines, each line contains n integers separated by single spaces. The i + 1-th row and j-th column contain number cij — the width of the pipe that goes from tank i to tank j (0 ≤ cij ≤ 106, cii = 0). If cij = 0, then there is no pipe from tank i to tank j.

## Output Format
Print a single integer — the maximum amount of water that can be transmitted from the main tank to the sewer tank per a unit of time.

## Examples
```input
5 7
0 1 0 2 0
0 0 4 10 0
0 0 0 0 5
0 0 0 0 10
0 0 0 0 0
```
```output
10
```
-----
```input
5 10
0 1 0 0 0
0 0 2 0 0
0 0 0 3 0
0 0 0 0 4
100 0 0 0 0
```
```output
5
```

## Note
In the first test Petya can increase width of the pipe that goes from the 1st to the 2nd water tank by 7 units.

In the second test Petya can increase width of the pipe that goes from the 1st to the 2nd water tank by 4 units, from the 2nd to the 3rd water tank by 3 units, from the 3rd to the 4th water tank by 2 units and from the 4th to 5th water tank by 1 unit.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Dima, Inna and Seryozha have gathered in a room. That's right, someone's got to go. To cheer Seryozha up and inspire him to have a walk, Inna decided to cook something.

Dima and Seryozha have n fruits in the fridge. Each fruit has two parameters: the taste and the number of calories. Inna decided to make a fruit salad, so she wants to take some fruits from the fridge for it. Inna follows a certain principle as she chooses the fruits: the total taste to the total calories ratio of the chosen fruits must equal k. In other words, $$\frac{\sum_{j=1}^{m}a_j}{\sum_{j=1}^{m}b_j}=k$$ , where aj is the taste of the j-th chosen fruit and bj is its calories.

Inna hasn't chosen the fruits yet, she is thinking: what is the maximum taste of the chosen fruits if she strictly follows her principle? Help Inna solve this culinary problem — now the happiness of a young couple is in your hands!

Inna loves Dima very much so she wants to make the salad from at least one fruit.

## Input Format
The first line of the input contains two integers n, k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10). The second line of the input contains n integers a1, a2, ..., an (1 ≤ ai ≤ 100) — the fruits' tastes. The third line of the input contains n integers b1, b2, ..., bn (1 ≤ bi ≤ 100) — the fruits' calories. Fruit number i has taste ai and calories bi.

## Output Format
If there is no way Inna can choose the fruits for the salad, print in the single line number -1. Otherwise, print a single integer — the maximum possible sum of the taste values of the chosen fruits.

## Examples
```input
3 2
10 8 1
2 7 1
```
```output
18
```
-----
```input
5 3
4 4 4 4 4
2 2 2 2 2
```
```output
-1
```

## Note
In the first test sample we can get the total taste of the fruits equal to 18 if we choose fruit number 1 and fruit number 2, then the total calories will equal 9. The condition $$\frac{18}{9}=2=k$$ fulfills, that's exactly what Inna wants.

In the second test sample we cannot choose the fruits so as to follow Inna's principle.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given matrix a of size n × m, its elements are integers. We will assume that the rows of the matrix are numbered from top to bottom from 1 to n, the columns are numbered from left to right from 1 to m. We will denote the element on the intersecting of the i-th row and the j-th column as aij.

We'll call submatrix i1, j1, i2, j2 (1 ≤ i1 ≤ i2 ≤ n; 1 ≤ j1 ≤ j2 ≤ m) such elements aij of the given matrix that i1 ≤ i ≤ i2 AND j1 ≤ j ≤ j2. We'll call the area of the submatrix number (i2 - i1 + 1)·(j2 - j1 + 1). We'll call a submatrix inhomogeneous, if all its elements are distinct.

Find the largest (in area) inhomogenous submatrix of the given matrix.

## Input Format
The first line contains two integers n, m (1 ≤ n, m ≤ 400) — the number of rows and columns of the matrix, correspondingly.

Each of the next n lines contains m integers aij (1 ≤ aij ≤ 160000) — the elements of the matrix.

## Output Format
Print a single integer — the area of the optimal inhomogenous submatrix.

## Examples
```input
3 3
1 3 1
4 5 6
2 6 1
```
```output
6
```
-----
```input
3 4
5 2 3 1
3 3 5 3
4 4 4 5
```
```output
4
```
-----
```input
2 6
1 2 3 4 5 6
8 6 7 8 9 1
```
```output
8
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
We'll call a sequence of integers a good k-d sequence if we can add to it at most k numbers in such a way that after the sorting the sequence will be an arithmetic progression with difference d.

You got hold of some sequence a, consisting of n integers. Your task is to find its longest contiguous subsegment, such that it is a good k-d sequence.

## Input Format
The first line contains three space-separated integers n, k, d (1 ≤ n ≤ 2·105; 0 ≤ k ≤ 2·105; 0 ≤ d ≤ 109). The second line contains n space-separated integers: a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the actual sequence.

## Output Format
Print two space-separated integers l, r (1 ≤ l ≤ r ≤ n) show that sequence al, al + 1, ..., ar is the longest subsegment that is a good k-d sequence.

If there are multiple optimal answers, print the one with the minimum value of l.

## Examples
```input
6 1 2
4 3 2 8 6 2
```
```output
3 5
```

## Note
In the first test sample the answer is the subsegment consisting of numbers 2, 8, 6 — after adding number 4 and sorting it becomes sequence 2, 4, 6, 8 — the arithmetic progression with difference 2.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
The hero of the Cut the Rope game is a little monster named Om Nom. He loves candies. And what a coincidence! He also is the hero of today's problem.

One day, Om Nom visited his friend Evan. Evan has n candies of two types (fruit drops and caramel drops), the i-th candy hangs at the height of hi centimeters above the floor of the house, its mass is mi. Om Nom wants to eat as many candies as possible. At the beginning Om Nom can make at most x centimeter high jumps. When Om Nom eats a candy of mass y, he gets stronger and the height of his jump increases by y centimeters.

What maximum number of candies can Om Nom eat if he never eats two candies of the same type in a row (Om Nom finds it too boring)?

## Input Format
The first line contains two integers, n and x (1 ≤ n, x ≤ 2000) — the number of sweets Evan has and the initial height of Om Nom's jump.

Each of the following n lines contains three integers ti, hi, mi (0 ≤ ti ≤ 1; 1 ≤ hi, mi ≤ 2000) — the type, height and the mass of the i-th candy. If number ti equals 0, then the current candy is a caramel drop, otherwise it is a fruit drop.

## Output Format
Print a single integer — the maximum number of candies Om Nom can eat.

## Examples
```input
5 3
0 2 4
1 3 1
0 8 3
0 20 10
1 5 5
```
```output
4
```

## Note
One of the possible ways to eat 4 candies is to eat them in the order: 1, 5, 3, 2. Let's assume the following scenario:

1. Initially, the height of Om Nom's jump equals 3. He can reach candies 1 and 2. Let's assume that he eats candy 1. As the mass of this candy equals 4, the height of his jump will rise to 3 + 4 = 7.
2. Now Om Nom can reach candies 2 and 5. Let's assume that he eats candy 5. Then the height of his jump will be 7 + 5 = 12.
3. At this moment, Om Nom can reach two candies, 2 and 3. He won't eat candy 2 as its type matches the type of the previously eaten candy. Om Nom eats candy 3, the height of his jump is 12 + 3 = 15.
4. Om Nom eats candy 2, the height of his jump is 15 + 1 = 16. He cannot reach candy 4.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 5.0 seconds
Memory limit: 256.0 MB

# Problem
Have you ever played Pudding Monsters? In this task, a simplified one-dimensional model of this game is used.

Imagine an infinite checkered stripe, the cells of which are numbered sequentially with integers. Some cells of the strip have monsters, other cells of the strip are empty. All monsters are made of pudding, so if there are two monsters in the neighboring cells, they stick to each other (literally). Similarly, if several monsters are on consecutive cells, they all stick together in one block of monsters. We will call the stuck together monsters a block of monsters. A detached monster, not stuck to anyone else, is also considered a block.

In one move, the player can take any block of monsters and with a movement of his hand throw it to the left or to the right. The selected monsters will slide on until they hit some other monster (or a block of monsters).

For example, if a strip has three monsters in cells 1, 4 and 5, then there are only four possible moves: to send a monster in cell 1 to minus infinity, send the block of monsters in cells 4 and 5 to plus infinity, throw monster 1 to the right (it will stop in cell 3), throw a block of monsters in cells 4 and 5 to the left (they will stop in cells 2 and 3).

Some cells on the strip are marked with stars. These are the special cells. The goal of the game is to make the largest possible number of special cells have monsters on them.

You are given the numbers of the special cells on a strip as well as the initial position of all monsters. What is the maximum number of special cells that will contain monsters in the optimal game?

## Input Format
The first line contains two integers n and m (1 ≤ n ≤ 105; 1 ≤ m ≤ 2000) — the number of monsters on the strip and the number of special cells.

The second line contains n distinct integers — the numbers of the cells with monsters, then the third line contains m distinct integers — the numbers of the special cells. It is guaranteed that all the numbers of the cells are positive integers not exceeding 2·105.

## Output Format
Print a single integer — the maximum number of special cells that will contain monsters in the optimal game.

## Examples
```input
3 2
1 3 5
2 4
```
```output
2
```
-----
```input
4 2
1 3 4 6
2 5
```
```output
2
```
-----
```input
4 2
1 8 4 5
7 2
```
```output
1
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 5.0 seconds
Memory limit: 256.0 MB

# Problem
Everyone who has played Cut the Rope knows full well how the gameplay is organized. All levels in the game are divided into boxes. Initially only one box with some levels is available. Player should complete levels to earn stars, collecting stars opens new box with levels.

Imagine that you are playing Cut the Rope for the first time. Currently you have only the levels of the first box (by the way, it is called "Cardboard Box"). Each level is characterized by two integers: ai — how long it takes to complete the level for one star, bi — how long it takes to complete the level for two stars (ai < bi).

You want to open the next box as quickly as possible. So, you need to earn at least w stars. How do make it happen? Note that the level can be passed only once: either for one star or for two. You do not necessarily need to pass all the levels.

## Input Format
The first line contains two integers n and w (1 ≤ n ≤ 3·105; 1 ≤ w ≤ 2n) — the number of levels in the first box and the number of stars you need to open another box. Each of the following n lines contains two integers ai and bi (1 ≤ ai < bi ≤ 109) — the attributes of the i-th level.

## Output Format
In the first line print integer t — the minimum time you need to open the next box.

In the next line, print n digits without spaces — the description of the optimal scenario:

- if you need to pass the i-th level for one star, the i-th digit should equal 1;
- if you need to pass the i-th level for two stars, the i-th digit should equal 2;
- if you do not need to pass the i-th level at all, the i-th digit should equal 0.

## Examples
```input
2 3
1 2
1 2
```
```output
3
12
```
-----
```input
5 3
10 20
5 10
10 20
6 9
25 30
```
```output
14
01020
```

## Note
In the first test sample, answer 21 is also assumed correct.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Bizon the Champion is called the Champion for a reason.

Bizon the Champion has recently got a present — a new glass cupboard with n shelves and he decided to put all his presents there. All the presents can be divided into two types: medals and cups. Bizon the Champion has a1 first prize cups, a2 second prize cups and a3 third prize cups. Besides, he has b1 first prize medals, b2 second prize medals and b3 third prize medals.

Naturally, the rewards in the cupboard must look good, that's why Bizon the Champion decided to follow the rules:

- any shelf cannot contain both cups and medals at the same time;
- no shelf can contain more than five cups;
- no shelf can have more than ten medals.

Help Bizon the Champion find out if we can put all the rewards so that all the conditions are fulfilled.

## Input Format
The first line contains integers a1, a2 and a3 (0 ≤ a1, a2, a3 ≤ 100). The second line contains integers b1, b2 and b3 (0 ≤ b1, b2, b3 ≤ 100). The third line contains integer n (1 ≤ n ≤ 100).

The numbers in the lines are separated by single spaces.

## Output Format
Print "YES" (without the quotes) if all the rewards can be put on the shelves in the described manner. Otherwise, print "NO" (without the quotes).

## Examples
```input
1 1 1
1 1 1
4
```
```output
YES
```
-----
```input
1 1 3
2 3 4
2
```
```output
YES
```
-----
```input
1 0 0
1 0 0
1
```
```output
NO
```

Now solve the problem and return the code.