meetforever/GRPO_CL huggingface dataset:
user: Limak is going to participate in a contest on the last day of the 2016. The contest will start at 20:00 and will last four hours, exactly until midnight. There will be n problems, sorted by difficulty, i.e. problem 1 is the easiest and problem n is the hardest. Limak knows it will take him 5·i minutes to solve the i-th problem.

Limak's friends organize a New Year's Eve party and Limak wants to be there at midnight or earlier. He needs k minutes to get there from his house, where he will participate in the contest first.

How many problems can Limak solve if he wants to make it to the party?


-----Input-----

The only line of the input contains two integers n and k (1 ≤ n ≤ 10, 1 ≤ k ≤ 240) — the number of the problems in the contest and the number of minutes Limak needs to get to the party from his house.


-----Output-----

Print one integer, denoting the maximum possible number of problems Limak can solve so that he could get to the party at midnight or earlier.


-----Examples-----
Input
3 222

Output
2

Input
4 190

Output
4

Input
7 1

Output
7



-----Note-----

In the first sample, there are 3 problems and Limak needs 222 minutes to get to the party. The three problems require 5, 10 and 15 minutes respectively. Limak can spend 5 + 10 = 15 minutes to solve first two problems. Then, at 20:15 he can leave his house to get to the party at 23:57 (after 222 minutes). In this scenario Limak would solve 2 problems. He doesn't have enough time to solve 3 problems so the answer is 2.

In the second sample, Limak can solve all 4 problems in 5 + 10 + 15 + 20 = 50 minutes. At 20:50 he will leave the house and go to the party. He will get there exactly at midnight.

In the third sample, Limak needs only 1 minute to get to the party. He has enough time to solve all 7 problems.
user: На тренировку по подготовке к соревнованиям по программированию пришли n команд. Тренер для каждой команды подобрал тренировку, комплект задач для i-й команды занимает a_{i} страниц. В распоряжении тренера есть x листов бумаги, у которых обе стороны чистые, и y листов, у которых только одна сторона чистая. При печати условия на листе первого типа можно напечатать две страницы из условий задач, а при печати на листе второго типа — только одну. Конечно, на листе нельзя печатать условия из двух разных комплектов задач. Обратите внимание, что при использовании листов, у которых обе стороны чистые, не обязательно печатать условие на обеих сторонах, одна из них может остаться чистой.

Вам предстоит определить максимальное количество команд, которым тренер сможет напечатать комплекты задач целиком.


-----Входные данные-----

В первой строке входных данных следуют три целых числа n, x и y (1 ≤ n ≤ 200 000, 0 ≤ x, y ≤ 10^9) — количество команд, количество листов бумаги с двумя чистыми сторонами и количество листов бумаги с одной чистой стороной.

Во второй строке входных данных следует последовательность из n целых чисел a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10 000), где i-е число равно количеству страниц в комплекте задач для i-й команды.


-----Выходные данные-----

Выведите единственное целое число — максимальное количество команд, которым тренер сможет напечатать комплекты задач целиком.


-----Примеры-----
Входные данные
2 3 5
4 6

Выходные данные
2

Входные данные
2 3 5
4 7

Выходные данные
2

Входные данные
6 3 5
12 11 12 11 12 11

Выходные данные
1



-----Примечание-----

В первом тестовом примере можно напечатать оба комплекта задач. Один из возможных ответов — напечатать весь первый комплект задач на листах с одной чистой стороной (после этого останется 3 листа с двумя чистыми сторонами и 1 лист с одной чистой стороной), а второй комплект напечатать на трех листах с двумя чистыми сторонами.

Во втором тестовом примере можно напечатать оба комплекта задач. Один из возможных ответов — напечатать первый комплект задач на двух листах с двумя чистыми сторонами (после этого останется 1 лист с двумя чистыми сторонами и 5 листов с одной чистой стороной), а второй комплект напечатать на одном листе с двумя чистыми сторонами и на пяти листах с одной чистой стороной. Таким образом, тренер использует все листы для печати.

В третьем тестовом примере можно напечатать только один комплект задач (любой из трёх 11-страничных). Для печати 11-страничного комплекта задач будет израсходована вся бумага.
user: Ivan has number $b$. He is sorting through the numbers $a$ from $1$ to $10^{18}$, and for every $a$ writes $\frac{[a, \,\, b]}{a}$ on blackboard. Here $[a, \,\, b]$ stands for least common multiple of $a$ and $b$. Ivan is very lazy, that's why this task bored him soon. But he is interested in how many different numbers he would write on the board if he would finish the task. Help him to find the quantity of different numbers he would write on the board.


-----Input-----

The only line contains one integer — $b$ $(1 \le b \le 10^{10})$.


-----Output-----

Print one number — answer for the problem.


-----Examples-----
Input
1

Output
1
Input
2

Output
2


-----Note-----

In the first example $[a, \,\, 1] = a$, therefore $\frac{[a, \,\, b]}{a}$ is always equal to $1$.

In the second example $[a, \,\, 2]$ can be equal to $a$ or $2 \cdot a$ depending on parity of $a$. $\frac{[a, \,\, b]}{a}$ can be equal to $1$ and $2$.
user: In a new version of the famous Pinball game, one of the most important parts of the game field is a sequence of n bumpers. The bumpers are numbered with integers from 1 to n from left to right. There are two types of bumpers. They are denoted by the characters '<' and '>'. When the ball hits the bumper at position i it goes one position to the right (to the position i + 1) if the type of this bumper is '>', or one position to the left (to i - 1) if the type of the bumper at position i is '<'. If there is no such position, in other words if i - 1 < 1 or i + 1 > n, the ball falls from the game field.

Depending on the ball's starting position, the ball may eventually fall from the game field or it may stay there forever. You are given a string representing the bumpers' types. Calculate the number of positions such that the ball will eventually fall from the game field if it starts at that position.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the length of the sequence of bumpers. The second line contains the string, which consists of the characters '<' and '>'. The character at the i-th position of this string corresponds to the type of the i-th bumper.


-----Output-----

Print one integer — the number of positions in the sequence such that the ball will eventually fall from the game field if it starts at that position.


-----Examples-----
Input
4
<<><

Output
2
Input
5
>>>>>

Output
5
Input
4
>><<

Output
0


-----Note-----

In the first sample, the ball will fall from the field if starts at position 1 or position 2.

In the second sample, any starting position will result in the ball falling from the field.
user: In the evening, after the contest Ilya was bored, and he really felt like maximizing. He remembered that he had a set of n sticks and an instrument. Each stick is characterized by its length l_{i}.

Ilya decided to make a rectangle from the sticks. And due to his whim, he decided to make rectangles in such a way that maximizes their total area. Each stick is used in making at most one rectangle, it is possible that some of sticks remain unused. Bending sticks is not allowed.

Sticks with lengths a_1, a_2, a_3 and a_4 can make a rectangle if the following properties are observed:  a_1 ≤ a_2 ≤ a_3 ≤ a_4  a_1 = a_2  a_3 = a_4 

A rectangle can be made of sticks with lengths of, for example, 3 3 3 3 or 2 2 4 4. A rectangle cannot be made of, for example, sticks 5 5 5 7.

Ilya also has an instrument which can reduce the length of the sticks. The sticks are made of a special material, so the length of each stick can be reduced by at most one. For example, a stick with length 5 can either stay at this length or be transformed into a stick of length 4.

You have to answer the question — what maximum total area of the rectangles can Ilya get with a file if makes rectangles from the available sticks?


-----Input-----

The first line of the input contains a positive integer n (1 ≤ n ≤ 10^5) — the number of the available sticks.

The second line of the input contains n positive integers l_{i} (2 ≤ l_{i} ≤ 10^6) — the lengths of the sticks.


-----Output-----

The first line of the output must contain a single non-negative integer — the maximum total area of the rectangles that Ilya can make from the available sticks.


-----Examples-----
Input
4
2 4 4 2

Output
8

Input
4
2 2 3 5

Output
0

Input
4
100003 100004 100005 100006

Output
10000800015
user: Petya has n positive integers a_1, a_2, ..., a_{n}. 

His friend Vasya decided to joke and replaced all digits in Petya's numbers with a letters. He used the lowercase letters of the Latin alphabet from 'a' to 'j' and replaced all digits 0 with one letter, all digits 1 with another letter and so on. For any two different digits Vasya used distinct letters from 'a' to 'j'.

Your task is to restore Petya's numbers. The restored numbers should be positive integers without leading zeros. Since there can be multiple ways to do it, determine the minimum possible sum of all Petya's numbers after the restoration. It is guaranteed that before Vasya's joke all Petya's numbers did not have leading zeros.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 1 000) — the number of Petya's numbers.

Each of the following lines contains non-empty string s_{i} consisting of lowercase Latin letters from 'a' to 'j' — the Petya's numbers after Vasya's joke. The length of each string does not exceed six characters.


-----Output-----

Determine the minimum sum of all Petya's numbers after the restoration. The restored numbers should be positive integers without leading zeros. It is guaranteed that the correct restore (without leading zeros) exists for all given tests.


-----Examples-----
Input
3
ab
de
aj

Output
47

Input
5
abcdef
ghij
bdef
accbd
g

Output
136542

Input
3
aa
jj
aa

Output
44



-----Note-----

In the first example, you need to replace the letter 'a' with the digit 1, the letter 'b' with the digit 0, the letter 'd' with the digit 2, the letter 'e' with the digit 3, and the letter 'j' with the digit 4. So after the restoration numbers will look like [10, 23, 14]. The sum of them is equal to 47, which is the minimum possible sum of the numbers after the correct restoration.

In the second example the numbers after the restoration can look like: [120468, 3579, 2468, 10024, 3]. 

In the second example the numbers after the restoration can look like: [11, 22, 11].
user: A and B are preparing themselves for programming contests.

An important part of preparing for a competition is sharing programming knowledge from the experienced members to those who are just beginning to deal with the contests. Therefore, during the next team training A decided to make teams so that newbies are solving problems together with experienced participants.

A believes that the optimal team of three people should consist of one experienced participant and two newbies. Thus, each experienced participant can share the experience with a large number of people.

However, B believes that the optimal team should have two experienced members plus one newbie. Thus, each newbie can gain more knowledge and experience.

As a result, A and B have decided that all the teams during the training session should belong to one of the two types described above. Furthermore, they agree that the total number of teams should be as much as possible.

There are n experienced members and m newbies on the training session. Can you calculate what maximum number of teams can be formed?


-----Input-----

The first line contains two integers n and m (0 ≤ n, m ≤ 5·10^5) — the number of experienced participants and newbies that are present at the training session. 


-----Output-----

Print the maximum number of teams that can be formed.


-----Examples-----
Input
2 6

Output
2

Input
4 5

Output
3



-----Note-----

Let's represent the experienced players as XP and newbies as NB.

In the first test the teams look as follows: (XP, NB, NB), (XP, NB, NB).

In the second test sample the teams look as follows: (XP, NB, NB), (XP, NB, NB), (XP, XP, NB).
user: You are given string s. Your task is to determine if the given string s contains two non-overlapping substrings "AB" and "BA" (the substrings can go in any order).


-----Input-----

The only line of input contains a string s of length between 1 and 10^5 consisting of uppercase Latin letters.


-----Output-----

Print "YES" (without the quotes), if string s contains two non-overlapping substrings "AB" and "BA", and "NO" otherwise.


-----Examples-----
Input
ABA

Output
NO

Input
BACFAB

Output
YES

Input
AXBYBXA

Output
NO



-----Note-----

In the first sample test, despite the fact that there are substrings "AB" and "BA", their occurrences overlap, so the answer is "NO".

In the second sample test there are the following occurrences of the substrings: BACFAB.

In the third sample test there is no substring "AB" nor substring "BA".
user: The Rebel fleet is afraid that the Empire might want to strike back again. Princess Heidi needs to know if it is possible to assign R Rebel spaceships to guard B bases so that every base has exactly one guardian and each spaceship has exactly one assigned base (in other words, the assignment is a perfect matching). Since she knows how reckless her pilots are, she wants to be sure that any two (straight) paths – from a base to its assigned spaceship – do not intersect in the galaxy plane (that is, in 2D), and so there is no risk of collision.


-----Input-----

The first line contains two space-separated integers R, B(1 ≤ R, B ≤ 10). For 1 ≤ i ≤ R, the i + 1-th line contains two space-separated integers x_{i} and y_{i} (|x_{i}|, |y_{i}| ≤ 10000) denoting the coordinates of the i-th Rebel spaceship. The following B lines have the same format, denoting the position of bases. It is guaranteed that no two points coincide and that no three points are on the same line.


-----Output-----

If it is possible to connect Rebel spaceships and bases so as satisfy the constraint, output Yes, otherwise output No (without quote).


-----Examples-----
Input
3 3
0 0
2 0
3 1
-2 1
0 3
2 2

Output
Yes

Input
2 1
1 0
2 2
3 1

Output
No



-----Note-----

For the first example, one possible way is to connect the Rebels and bases in order.

For the second example, there is no perfect matching between Rebels and bases.
user: Поликарп мечтает стать программистом и фанатеет от степеней двойки. Среди двух чисел ему больше нравится то, которое делится на большую степень числа 2. 

По заданной последовательности целых положительных чисел a_1, a_2, ..., a_{n} требуется найти r — максимальную степень числа 2, на которую делится хотя бы одно из чисел последовательности. Кроме того, требуется вывести количество чисел a_{i}, которые делятся на r.


-----Входные данные-----

В первой строке записано целое число n (1 ≤ n ≤ 100) — длина последовательности a.

Во второй строке записана последовательность целых чисел a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Выходные данные-----

Выведите два числа:

  r — максимальную степень двойки, на которую делится хотя бы одно из чисел заданной последовательности,  количество элементов последовательности, которые делятся на r. 


-----Примеры-----
Входные данные
5
80 7 16 4 48

Выходные данные
16 3

Входные данные
4
21 5 3 33

Выходные данные
1 4



-----Примечание-----

В первом тестовом примере максимальная степень двойки, на которую делится хотя бы одно число, равна 16 = 2^4, на неё делятся числа 80, 16 и 48.

Во втором тестовом примере все четыре числа нечётные, поэтому делятся только на 1 = 2^0. Это и будет максимальной степенью двойки для данного примера.
user: Vasya has found a strange device. On the front panel of a device there are: a red button, a blue button and a display showing some positive integer. After clicking the red button, device multiplies the displayed number by two. After clicking the blue button, device subtracts one from the number on the display. If at some point the number stops being positive, the device breaks down. The display can show arbitrarily large numbers. Initially, the display shows number n.

Bob wants to get number m on the display. What minimum number of clicks he has to make in order to achieve this result?


-----Input-----

The first and the only line of the input contains two distinct integers n and m (1 ≤ n, m ≤ 10^4), separated by a space .


-----Output-----

Print a single number — the minimum number of times one needs to push the button required to get the number m out of number n.


-----Examples-----
Input
4 6

Output
2

Input
10 1

Output
9



-----Note-----

In the first example you need to push the blue button once, and then push the red button once.

In the second example, doubling the number is unnecessary, so we need to push the blue button nine times.
user: As the name of the task implies, you are asked to do some work with segments and trees.

Recall that a tree is a connected undirected graph such that there is exactly one simple path between every pair of its vertices.

You are given $n$ segments $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$, $l_i < r_i$ for every $i$. It is guaranteed that all segments' endpoints are integers, and all endpoints are unique — there is no pair of segments such that they start in the same point, end in the same point or one starts in the same point the other one ends.

Let's generate a graph with $n$ vertices from these segments. Vertices $v$ and $u$ are connected by an edge if and only if segments $[l_v, r_v]$ and $[l_u, r_u]$ intersect and neither of it lies fully inside the other one.

For example, pairs $([1, 3], [2, 4])$ and $([5, 10], [3, 7])$ will induce the edges but pairs $([1, 2], [3, 4])$ and $([5, 7], [3, 10])$ will not.

Determine if the resulting graph is a tree or not.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the number of segments.

The $i$-th of the next $n$ lines contain the description of the $i$-th segment — two integers $l_i$ and $r_i$ ($1 \le l_i < r_i \le 2n$).

It is guaranteed that all segments borders are pairwise distinct. 


-----Output-----

Print "YES" if the resulting graph is a tree and "NO" otherwise.


-----Examples-----
Input
6
9 12
2 11
1 3
6 10
5 7
4 8

Output
YES

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

Output
NO

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

Output
NO



-----Note-----

The graph corresponding to the first example:

[Image]

The graph corresponding to the second example:

[Image]

The graph corresponding to the third example:

[Image]
user: We get more and more news about DDoS-attacks of popular websites.

Arseny is an admin and he thinks that a website is under a DDoS-attack if the total number of requests for a some period of time exceeds $100 \cdot t$, where $t$ — the number of seconds in this time segment. 

Arseny knows statistics on the number of requests per second since the server is booted. He knows the sequence $r_1, r_2, \dots, r_n$, where $r_i$ — the number of requests in the $i$-th second after boot. 

Determine the length of the longest continuous period of time, which Arseny considers to be a DDoS-attack. A seeking time period should not go beyond the boundaries of the segment $[1, n]$.


-----Input-----

The first line contains $n$ ($1 \le n \le 5000$) — number of seconds since server has been booted. The second line contains sequence of integers $r_1, r_2, \dots, r_n$ ($0 \le r_i \le 5000$), $r_i$ — number of requests in the $i$-th second.


-----Output-----

Print the only integer number — the length of the longest time period which is considered to be a DDoS-attack by Arseny. If it doesn't exist print 0.


-----Examples-----
Input
5
100 200 1 1 1

Output
3

Input
5
1 2 3 4 5

Output
0

Input
2
101 99

Output
1
user: Well, the series which Stepan watched for a very long time, ended. In total, the series had n episodes. For each of them, Stepan remembers either that he definitely has watched it, or that he definitely hasn't watched it, or he is unsure, has he watched this episode or not. 

Stepan's dissatisfaction is the maximum number of consecutive series that Stepan did not watch.

Your task is to determine according to Stepan's memories if his dissatisfaction could be exactly equal to k.


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ n) — the number of episodes in the series and the dissatisfaction which should be checked. 

The second line contains the sequence which consists of n symbols "Y", "N" and "?". If the i-th symbol equals "Y", Stepan remembers that he has watched the episode number i. If the i-th symbol equals "N", Stepan remembers that he hasn't watched the epizode number i. If the i-th symbol equals "?", Stepan doesn't exactly remember if he has watched the episode number i or not.


-----Output-----

If Stepan's dissatisfaction can be exactly equal to k, then print "YES" (without qoutes). Otherwise print "NO" (without qoutes).


-----Examples-----
Input
5 2
NYNNY

Output
YES

Input
6 1
????NN

Output
NO



-----Note-----

In the first test Stepan remembers about all the episodes whether he has watched them or not. His dissatisfaction is 2, because he hasn't watch two episodes in a row — the episode number 3 and the episode number 4. The answer is "YES", because k = 2.

In the second test k = 1, Stepan's dissatisfaction is greater than or equal to 2 (because he remembers that he hasn't watch at least two episodes in a row — number 5 and number 6), even if he has watched the episodes from the first to the fourth, inclusive.
user: We have an integer sequence A of length N, where A_1 = X, A_{i+1} = A_i + D (1 \leq  i < N ) holds.
Takahashi will take some (possibly all or none) of the elements in this sequence, and Aoki will take all of the others.
Let S and T be the sum of the numbers taken by Takahashi and Aoki, respectively. How many possible values of S - T are there?

-----Constraints-----
 - -10^8 \leq X, D \leq 10^8
 - 1 \leq N \leq 2 \times 10^5
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N X D

-----Output-----
Print the number of possible values of S - T.

-----Sample Input-----
3 4 2

-----Sample Output-----
8

A is (4, 6, 8).
There are eight ways for (Takahashi, Aoki) to take the elements: ((), (4, 6, 8)), ((4), (6, 8)), ((6), (4, 8)), ((8), (4, 6))), ((4, 6), (8))), ((4, 8), (6))), ((6, 8), (4))), and ((4, 6, 8), ()).
The values of S - T in these ways are -18, -10, -6, -2, 2, 6, 10, and 18, respectively, so there are eight possible values of S - T.