루미 알고리즘

#1567실버Plankton

PO 2023 온라인 예선코딩출제 Johan Sannemo, Nicole Hedblom영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

The fishes Alexa and Boris are going to start a plankton farm at the bottom of the sea. To prevent the plankton from escaping, they want to build rectangular enclosures surrounded by fences. Each enclosure must have an area of at least A cm^2 so that the plankton has enough space to grow.

The fence for a given enclosure is set up along its entire perimeter in the form of four pre-built pieces: a pair of equally long horizontal pieces and a pair of equally long vertical pieces. Alexa and Boris have already purchased several pairs of fence pieces, where the pieces in each pair are of equal length. They now want to build as many enclosures with an area of at least A cm^2 as possible. Can you help them calculate how many enclosures they can build simultaneously with their fence pieces?

Input

The first line of input contains the integer A (1 ≤ A ≤ 10^9), the minimum area that each enclosure must have.

The next line contains an integer N (1 ≤ N ≤ 100,000), the number of pairs of fence pieces that Alexa and Boris have already purchased.

The last line contains N integers l_1, l_2, …, l_N (1 ≤ l_i ≤ 10^9), where l_i is the length of the pieces in the i-th pair they bought, measured in centimeters.

Output

Print an integer: the largest number of enclosures that Alexa and Boris can build using their fence pieces.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
120The group consists of a single subtask, the one on our poster (https://www.progolymp.se/2023/affisch.pdf).
212N ≤ 300
328N ≤ 2000
429A ≤ 2000
511No additional constraints.

Explanation of sample

In the first example case, a maximum of 2 enclosures can be built. For example, one can choose the pairs of fence pieces with lengths of 5 cm and 13 cm (with an area of 5 cm × 13 cm = 65 cm^2) and the pairs with lengths of 8 cm and 21 cm (with an area of 8 cm × 21 cm = 168 cm^2), both of which are at least 40 cm^2.

In the second example case, all pairs of fence pieces have the same length. However, with this length, the enclosure has an area of 100 cm^2, which is just slightly too small.

In the third case, Alexa and Boris are satisfied with an area of 100 cm^2, so all pairs of fence pieces can be used to build a total of 5 enclosures.

예제

예제 1

입력
40
8
21 3 13 1 2 1 8 5
출력
2

예제 2

입력
101
10
10 10 10 10 10 10 10 10 10 10
출력
0

예제 3

입력
100
10
10 10 10 10 10 10 10 10 10 10
출력
5

예제 4

입력
80
9
4 3 10 27 3 50 19 5 1
출력
3

출처 표기

출처: Programmeringsolympiaden 2023년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.