COCI 2013/2014 Contest 1 Task 5 ORGANIZATOR- 대회 > 문제은행 : 정보올림피아드&알고리즘




2735 : 대회

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
3 회   
시도횟수
46 회   

문제

플루오르 대륙에서 대륙단위 대회를 주최하였다. 이 대회는 예선과 결선으로 이루어지며, 팀 단위 시합이다. 한편, 한 팀에는 무조건 L명의 용사들로만 구성되어야 한다. L은 주최 측에서 결정하는 수이다. 만약 L=1이면 이 대회는 개인전이다.



플루오르 대륙에는 N개의 마을이 있는데, 각 마을에는 Pk명의 용사들이 있다. 각 마을에서는 용사들을 L명씩 묶어서 팀을 만든 후, 그 팀들 중에서 가장 강한 팀을 뽑아서 그 팀만을 결선에 내보낸다. 만약 예선에 참여하지 못하는 용사가 있을 경우(즉, Pk가 L의 배수가 아닐 경우)에는 공정성을 위해 그 마을에서 결선 진출 팀을 내보내지 않는다.



한편, 결선에서는 예선에서 승리한 팀들을 대상으로 다시 시합을 해서 가장 강한 팀을 뽑는다. 이 때, 결선에 진출한 팀은 두 팀 이상이여야 한다.



민규는 이 대회에서 L을 결정하는 역할을 맡았다. 대회가 성대하게 진행되려면 결선에 진출하는 용사의 수가 최대한 많아야 한다. 플루오르 대륙에는 마을이 너무 많기 때문에 손으로 L을 구하기는 힘들다. 민규를 위해 L을 구해주는 프로그램을 만들자.

 

 


입력형식

첫 번째 줄에는 마을의 수 N이 주어진다. (2 ≤ N ≤ 200,000) 두 번째 줄에는 각 마을의 인구 Pk가 주어진다. (1 ≤ Pk ≤ 2,000,000)

출력형식

결선에 진출하는 용사의 수의 최댓값을 출력한다.

입력 예

3
1 2 4

출력 예

4

입력 예

2
1 5

출력 예

2

입력 예

5
4 6 3 8 9

출력 예

9


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP