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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 64.0 MB

# Problem
You can preview the image in better quality by the link: http://assets.codeforces.com/files/656/without-text.png

## Input Format
The only line of the input is a string (between 1 and 50 characters long, inclusive). Each character will be an alphanumeric character or a full stop ".".

## Output Format
Output the required answer.

## Examples
```input
Codeforces
```
```output
-87
```
-----
```input
APRIL.1st
```
```output
17
```

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 64.0 MB

# Problem
You are given a complete undirected graph. For each pair of vertices you are given the length of the edge that connects them. Find the shortest paths between each pair of vertices in the graph and return the length of the longest of them.

## Input Format
The first line of the input contains a single integer N (3 ≤ N ≤ 10).

The following N lines each contain N space-separated integers. jth integer in ith line aij is the length of the edge that connects vertices i and j. aij = aji, aii = 0, 1 ≤ aij ≤ 100 for i ≠ j.

## Output Format
Output the maximum length of the shortest path between any pair of vertices in the graph.

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

## Note
You're running short of keywords, so you can't use some of them:

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 64.0 MB

# Problem
A simple recommendation system would recommend a user things liked by a certain number of their friends. In this problem you will implement part of such a system.

You are given user's friends' opinions about a list of items. You are also given a threshold T — the minimal number of "likes" necessary for an item to be recommended to the user.

Output the number of items in the list liked by at least T of user's friends.

## Input Format
The first line of the input will contain three space-separated integers: the number of friends F (1 ≤ F ≤ 10), the number of items I (1 ≤ I ≤ 10) and the threshold T (1 ≤ T ≤ F).

The following F lines of input contain user's friends' opinions. j-th character of i-th line is 'Y' if i-th friend likes j-th item, and 'N' otherwise.

## Output Format
Output an integer — the number of items liked by at least T of user's friends.

## Examples
```input
3 3 2
YYY
NNN
YNY
```
```output
2
```
-----
```input
4 4 1
NNNY
NNYN
NYNN
YNNN
```
```output
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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
As some of you know, cubism is a trend in art, where the problem of constructing volumetrical shape on a plane with a combination of three-dimensional geometric shapes comes to the fore.

A famous sculptor Cicasso, whose self-portrait you can contemplate, hates cubism. He is more impressed by the idea to transmit two-dimensional objects through three-dimensional objects by using his magnificent sculptures. And his new project is connected with this. Cicasso wants to make a coat for the haters of anticubism. To do this, he wants to create a sculpture depicting a well-known geometric primitive — convex polygon.

Cicasso prepared for this a few blanks, which are rods with integer lengths, and now he wants to bring them together. The i-th rod is a segment of length li.

The sculptor plans to make a convex polygon with a nonzero area, using all rods he has as its sides. Each rod should be used as a side to its full length. It is forbidden to cut, break or bend rods. However, two sides may form a straight angle $$180^\circ$$.

Cicasso knows that it is impossible to make a convex polygon with a nonzero area out of the rods with the lengths which he had chosen. Cicasso does not want to leave the unused rods, so the sculptor decides to make another rod-blank with an integer length so that his problem is solvable. Of course, he wants to make it as short as possible, because the materials are expensive, and it is improper deed to spend money for nothing.

Help sculptor!

## Input Format
The first line contains an integer n (3 ≤ n ≤ 105) — a number of rod-blanks.

The second line contains n integers li (1 ≤ li ≤ 109) — lengths of rods, which Cicasso already has. It is guaranteed that it is impossible to make a polygon with n vertices and nonzero area using the rods Cicasso already has.

## Output Format
Print the only integer z — the minimum length of the rod, so that after adding it it can be possible to construct convex polygon with (n + 1) vertices and nonzero area from all of the rods.

## Examples
```input
3
1 2 1
```
```output
1
```
-----
```input
5
20 4 3 2 1
```
```output
11
```

## Note
In the first example triangle with sides {1 + 1 = 2, 2, 1} can be formed from a set of lengths {1, 1, 1, 2}.

In the second example you can make a triangle with lengths {20, 11, 4 + 3 + 2 + 1 = 10}.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Bear Limak likes watching sports on TV. He is going to watch a game today. The game lasts 90 minutes and there are no breaks.

Each minute can be either interesting or boring. If 15 consecutive minutes are boring then Limak immediately turns TV off.

You know that there will be n interesting minutes t1, t2, ..., tn. Your task is to calculate for how many minutes Limak will watch the game.

## Input Format
The first line of the input contains one integer n (1 ≤ n ≤ 90) — the number of interesting minutes.

The second line contains n integers t1, t2, ..., tn (1 ≤ t1 < t2 < ... tn ≤ 90), given in the increasing order.

## Output Format
Print the number of minutes Limak will watch the game.

## Examples
```input
3
7 20 88
```
```output
35
```
-----
```input
9
16 20 30 40 50 60 70 80 90
```
```output
15
```
-----
```input
9
15 20 30 40 50 60 70 80 90
```
```output
90
```

## Note
In the first sample, minutes 21, 22, ..., 35 are all boring and thus Limak will turn TV off immediately after the 35-th minute. So, he would watch the game for 35 minutes.

In the second sample, the first 15 minutes are boring.

In the third sample, there are no consecutive 15 boring minutes. So, Limak will watch the whole game.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
There are n problems prepared for the next Codeforces round. They are arranged in ascending order by their difficulty, and no two problems have the same difficulty. Moreover, there are m pairs of similar problems. Authors want to split problems between two division according to the following rules:

- Problemset of each division should be non-empty.
- Each problem should be used in exactly one division (yes, it is unusual requirement).
- Each problem used in division 1 should be harder than any problem used in division 2.
- If two problems are similar, they should be used in different divisions.

Your goal is count the number of ways to split problem between two divisions and satisfy all the rules. Two ways to split problems are considered to be different if there is at least one problem that belongs to division 1 in one of them and to division 2 in the other.

Note, that the relation of similarity is not transitive. That is, if problem i is similar to problem j and problem j is similar to problem k, it doesn't follow that i is similar to k.

## Input Format
The first line of the input contains two integers n and m (2 ≤ n ≤ 100 000, 0 ≤ m ≤ 100 000) — the number of problems prepared for the round and the number of pairs of similar problems, respectively.

Each of the following m lines contains a pair of similar problems ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi). It's guaranteed, that no pair of problems meets twice in the input.

## Output Format
Print one integer — the number of ways to split problems in two divisions.

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

## Note
In the first sample, problems 1 and 2 should be used in division 2, while problems 4 and 5 in division 1. Problem 3 may be used either in division 1 or in division 2.

In the second sample, all pairs of problems are similar and there is no way to split problem between two divisions without breaking any rules.

Third sample reminds you that the similarity relation is not transitive. Problem 3 is similar to both 1 and 2, but 1 is not similar to 2, so they may be used together.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
After finishing eating her bun, Alyona came up with two integers n and m. She decided to write down two columns of integers — the first column containing integers from 1 to n and the second containing integers from 1 to m. Now the girl wants to count how many pairs of integers she can choose, one from the first column and the other from the second column, such that their sum is divisible by 5.

Formally, Alyona wants to count the number of pairs of integers (x, y) such that 1 ≤ x ≤ n, 1 ≤ y ≤ m and $$(x+y) \mod 5$$ equals 0.

As usual, Alyona has some troubles and asks you to help.

## Input Format
The only line of the input contains two integers n and m (1 ≤ n, m ≤ 1 000 000).

## Output Format
Print the only integer — the number of pairs of integers (x, y) such that 1 ≤ x ≤ n, 1 ≤ y ≤ m and (x + y) is divisible by 5.

## Examples
```input
6 12
```
```output
14
```
-----
```input
11 14
```
```output
31
```
-----
```input
1 5
```
```output
1
```
-----
```input
3 8
```
```output
5
```
-----
```input
5 7
```
```output
7
```
-----
```input
21 21
```
```output
88
```

## Note
Following pairs are suitable in the first sample case:

- for x = 1 fits y equal to 4 or 9;
- for x = 2 fits y equal to 3 or 8;
- for x = 3 fits y equal to 2, 7 or 12;
- for x = 4 fits y equal to 1, 6 or 11;
- for x = 5 fits y equal to 5 or 10;
- for x = 6 fits y equal to 4 or 9.

Only the pair (1, 4) is suitable in the third sample case.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Someone gave Alyona an array containing n positive integers a1, a2, ..., an. In one operation, Alyona can choose any element of the array and decrease it, i.e. replace with any positive integer that is smaller than the current one. Alyona can repeat this operation as many times as she wants. In particular, she may not apply any operation to the array at all.

Formally, after applying some operations Alyona will get an array of n positive integers b1, b2, ..., bn such that 1 ≤ bi ≤ ai for every 1 ≤ i ≤ n. Your task is to determine the maximum possible value of mex of this array.

Mex of an array in this problem is the minimum positive integer that doesn't appear in this array. For example, mex of the array containing 1, 3 and 4 is equal to 2, while mex of the array containing 2, 3 and 2 is equal to 1.

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of elements in the Alyona's array.

The second line of the input contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the array.

## Output Format
Print one positive integer — the maximum possible value of mex of the array after Alyona applies some (possibly none) operations.

## Examples
```input
5
1 3 3 3 6
```
```output
5
```
-----
```input
2
2 1
```
```output
3
```

## Note
In the first sample case if one will decrease the second element value to 2 and the fifth element value to 4 then the mex value of resulting array 1 2 3 3 4 will be equal to 5.

To reach the answer to the second sample case one must not decrease any of the array elements.

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 python3.

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:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Alyona decided to go on a diet and went to the forest to get some apples. There she unexpectedly found a magic rooted tree with root in the vertex 1, every vertex and every edge of which has a number written on.

The girl noticed that some of the tree's vertices are sad, so she decided to play with them. Let's call vertex v sad if there is a vertex u in subtree of vertex v such that dist(v, u) > au, where au is the number written on vertex u, dist(v, u) is the sum of the numbers written on the edges on the path from v to u.

Leaves of a tree are vertices connected to a single vertex by a single edge, but the root of a tree is a leaf if and only if the tree consists of a single vertex — root.

Thus Alyona decided to remove some of tree leaves until there will be no any sad vertex left in the tree. What is the minimum number of leaves Alyona needs to remove?

## Input Format
In the first line of the input integer n (1 ≤ n ≤ 105) is given — the number of vertices in the tree.

In the second line the sequence of n integers a1, a2, ..., an (1 ≤ ai ≤ 109) is given, where ai is the number written on vertex i.

The next n - 1 lines describe tree edges: ith of them consists of two integers pi and ci (1 ≤ pi ≤ n,  - 109 ≤ ci ≤ 109), meaning that there is an edge connecting vertices i + 1 and pi with number ci written on it.

## Output Format
Print the only integer — the minimum number of leaves Alyona needs to remove such that there will be no any sad vertex left in the tree.

## Examples
```input
9
88 22 83 14 95 91 98 53 11
3 24
7 -8
1 67
1 64
9 65
5 12
6 -80
3 8
```
```output
5
```

## Note
The following image represents possible process of removing leaves from the tree:

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 python3.

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:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
After returned from forest, Alyona started reading a book. She noticed strings s and t, lengths of which are n and m respectively. As usual, reading bored Alyona and she decided to pay her attention to strings s and t, which she considered very similar.

Alyona has her favourite positive integer k and because she is too small, k does not exceed 10. The girl wants now to choose k disjoint non-empty substrings of string s such that these strings appear as disjoint substrings of string t and in the same order as they do in string s. She is also interested in that their length is maximum possible among all variants.

Formally, Alyona wants to find a sequence of k non-empty strings p1, p2, p3, ..., pk satisfying following conditions:

- s can be represented as concatenation a1p1a2p2... akpkak + 1, where a1, a2, ..., ak + 1 is a sequence of arbitrary strings (some of them may be possibly empty);
- t can be represented as concatenation b1p1b2p2... bkpkbk + 1, where b1, b2, ..., bk + 1 is a sequence of arbitrary strings (some of them may be possibly empty);
- sum of the lengths of strings in sequence is maximum possible.

Please help Alyona solve this complicated problem and find at least the sum of the lengths of the strings in a desired sequence.

A substring of a string is a subsequence of consecutive characters of the string.

## Input Format
In the first line of the input three integers n, m, k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10) are given — the length of the string s, the length of the string t and Alyona's favourite number respectively.

The second line of the input contains string s, consisting of lowercase English letters.

The third line of the input contains string t, consisting of lowercase English letters.

## Output Format
In the only line print the only non-negative integer — the sum of the lengths of the strings in a desired sequence.

It is guaranteed, that at least one desired sequence exists.

## Examples
```input
3 2 2
abc
ab
```
```output
2
```
-----
```input
9 12 4
bbaaababb
abbbabbaaaba
```
```output
7
```

## Note
The following image describes the answer for the second sample case:

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 python3.

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:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given n points with integer coordinates on the plane. Points are given in a way such that there is no triangle, formed by any three of these n points, which area exceeds S.

Alyona tried to construct a triangle with integer coordinates, which contains all n points and which area doesn't exceed 4S, but, by obvious reason, had no success in that. Please help Alyona construct such triangle. Please note that vertices of resulting triangle are not necessarily chosen from n given points.

## Input Format
In the first line of the input two integers n and S (3 ≤ n ≤ 5000, 1 ≤ S ≤ 1018) are given — the number of points given and the upper bound value of any triangle's area, formed by any three of given n points.

The next n lines describes given points: ith of them consists of two integers xi and yi ( - 108 ≤ xi, yi ≤ 108) — coordinates of ith point.

It is guaranteed that there is at least one triple of points not lying on the same line.

## Output Format
Print the coordinates of three points — vertices of a triangle which contains all n points and which area doesn't exceed 4S.

Coordinates of every triangle's vertex should be printed on a separate line, every coordinate pair should be separated by a single space. Coordinates should be an integers not exceeding 109 by absolute value.

It is guaranteed that there is at least one desired triangle. If there is more than one answer, print any of them.

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

Now solve the problem and return the code.