TeachingCompetitive ProgrammingCP - Session 1
Week 1Workshop

CP - Session 1

CP LA01 — Session 1: Recursion & Sorting

Practice contest covering Session 1 topics: Complexity Analysis, Problem Solving Paradigms (Complete Search, Greedy), Sorting, and Ad Hoc / Recursion-related simulation.

How to Join

  1. Create a Vjudge account (if you don't have one yet) at vjudge.net — click Sign Up, fill in your username, email, and password. No approval needed, you can start immediately.
  2. Open the contest link: vjudge.net/contest/848122
  3. Enter the password when prompted: [PASSWORD]
  4. Once inside, you'll see 5 problems (A–E), a countdown/running timer, and a live scoreboard.
  5. Click a problem, read the statement, write your solution, select C++ (GNU G++17/20/23) as the language, and submit.
  6. You may submit multiple times — only your best verdict counts toward the scoreboard.

Rules:

  • Work individually.
  • Standard verdicts apply: Accepted (AC), Wrong Answer (WA), Time Limit Exceeded (TLE), Runtime Error (RE).
  • Ranking follows ICPC rules: most problems solved first, then lowest total penalty time.

Problem Set

Alias Code Title Topic Rating
A 4A Watermelon Complexity (warm-up) 800
B 231A Team Complete Search 800
C 158A Next Round Sorting 800
D 977A Wrong Subtraction Ad Hoc / Simulation 900
E 158B Taxi Greedy 1100

A. Watermelon

Time limit: 1 second Memory limit: 64 megabytes

One hot summer day Pete and his friend Billy decided to buy a watermelon. They chose the biggest and the ripest one, in their opinion. After that the watermelon was weighed, and the scales showed w kilos. They rushed home, dying of thirst, and decided to divide the berry, however they faced a hard problem.

Pete and Billy are great fans of even numbers, that's why they want to divide the watermelon in such a way that each of the two parts weighs even number of kilos, at the same time it is not obligatory that the parts are equal. The boys are extremely tired and want to start their meal as soon as possible, that's why you should help them and find out, if they can divide the watermelon in the way they want. For sure, each of them should get a part of positive weight.

Input

The first (and the only) input line contains integer number w (1 ≤ w ≤ 100) — the weight of the watermelon bought by the boys.

Output

Print YES, if the boys can divide the watermelon into two parts, each of them weighing even number of kilos; and NO in the opposite case.

Example

Input

8

Output

YES

Note: For example, the boys can divide the watermelon into two parts of 2 and 6 kilos respectively (another variant — two parts of 4 and 4 kilos).

B. Team

Time limit: 2 seconds Memory limit: 256 megabytes

One day three best friends Petya, Vasya and Tonya decided to form a team and take part in programming contests. Participants are usually offered several problems during programming contests. Long before the start the friends decided that they will implement a problem if at least two of them are sure about the solution. Otherwise, the friends won't write the problem's solution.

This contest offers n problems to the participants. For each problem we know, which friend is sure about the solution. Help the friends find the number of problems for which they will write a solution.

Input

The first input line contains a single integer n (1 ≤ n ≤ 1000) — the number of problems in the contest. Then n lines contain three integers each, each integer is either 0 or 1. If the first number in the line equals 1, then Petya is sure about the problem's solution, otherwise he isn't sure. The second number shows Vasya's view on the solution, the third number shows Tonya's view. The numbers on the lines are separated by spaces.

Output

Print a single integer — the number of problems the friends will implement on the contest.

Example

Input

3
1 1 0
1 1 1
1 0 0

Output

2

Note: In the first sample Petya and Vasya are sure that they know how to solve the first problem and all three of them know how to solve the second problem. That means that they will write solutions for these problems. Only Petya is sure about the solution for the third problem, but that isn't enough, so the friends won't take it.

C. Next Round

Time limit: 3 seconds Memory limit: 256 megabytes

"Contestant who earns a score equal to or greater than the k-th place finisher's score will advance to the next round, as long as the contestant earns a positive score..." — an excerpt from contest rules.

A total of n participants took part in the contest (n ≥ k), and you already know their scores. Calculate how many participants will advance to the next round.

Input

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 50) separated by a single space.

The second line contains n space-separated integers a₁, a₂, ..., aₙ (0 ≤ aᵢ ≤ 100), where aᵢ is the score earned by the participant who got the i-th place. The given sequence is non-increasing (that is, for all i from 1 to n − 1 the following condition is fulfilled: aᵢ ≥ aᵢ₊₁).

Output

Output the number of participants who advance to the next round.

Example

Input

8 5
10 9 8 7 7 7 5 5

Output

6

Note: In the example the participant on the 5th place earned 7 points. As the participant on the 6th place also earned 7 points, there are 6 advancers.

D. Wrong Subtraction

Time limit: 1 second Memory limit: 256 megabytes

Little girl Tanya is learning how to decrease a number by one, but she does it wrong with a number consisting of two or more digits. Tanya subtracts one from a number by the following algorithm:

  • if the last digit of the number is non-zero, she decreases the number by one;
  • if the last digit of the number is zero, she divides the number by 10 (i.e. removes the last digit).

You are given an integer number n. Tanya will subtract one from it k times. Your task is to print the result after all k subtractions.

It is guaranteed that the result will be positive integer number.

Input

The first line of the input contains two integer numbers n and k (2 ≤ n ≤ 10⁹, 1 ≤ k ≤ 50) — the number from which Tanya will subtract and the number of subtractions correspondingly.

Output

Print one integer number — the result of the decreasing n by one k times.

Example

Input

512 4

Output

50

Note: The first example corresponds to the following sequence: 512 → 511 → 510 → 51 → 50.

E. Taxi

Time limit: 3 seconds Memory limit: 256 megabytes

After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of sᵢ friends (1 ≤ sᵢ ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?

Input

The first line contains integer n (1 ≤ n ≤ 10⁵) — the number of groups of schoolchildren. The second line contains a sequence of integers s₁, s₂, ..., sₙ (1 ≤ sᵢ ≤ 4). The integers are separated by a space, sᵢ is the number of children in the i-th group.

Output

Print the single number — the minimum number of taxis necessary to drive all children to Polycarpus.

Example

Input

5
1 2 4 3 3

Output

4

Note: In the first test we can sort the children into four cars like this:

  • the third group (consisting of four children),
  • the fourth group (consisting of three children),
  • the fifth group (consisting of three children),
  • the first and the second group (consisting of one and two children, correspondingly).

There are other ways to sort the groups into four cars.