JOI 2011/2012 예선 3- 베스트 피자(Best Pizza) > 문제은행 : 정보올림피아드&알고리즘




2931 : 베스트 피자(Best Pizza)

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

문제

올해도 꿀꿀이 올림피아드 대회가 열린다. 대회를 위한 예비 심사에서 많은 꿀꿀이들이 무난히 심사를 통과했지만 앙데용꿀꿀이 은비는 예비심사를 통과하지 못했다. 이유는 꿀꿀이라고 하기에는 너무 날씬했기 때문이다.

 

예비심사에서 떨어진 은비는 10일 후에 있을 추가 심사에는 꼭 통과하기로 결심하고 살을 찌울 계획을 세웠다. 하지만 그 짧은 시간에 필요한 만큼의 살을 찌우려면 '비게로만'이나 '살로우만' 같은 최고의 트레이너를 고용해야 해서 너무 많은 비용이 필요하였다. 

 

너무 속상하여 엉엉 울고 있었는데 마침 그 옆을 지나가던 엉뚱꿀꿀이 송뒤뚱이 자초지종을 물었다. 

사정을 듣고 난 송뒤뚱은 '이거 비밀인데 1번가 APM(Ace Pig Master)피자집에가서 베스트 피자를 먹어 보는건 어떨까? '하고는 뒤뚱거리며 갈길을 갔다. 

 

APM피자에서는 도우는 한 종류이지만  가격이 모두 같은 토핑이 N종류 있다. N개의 토핑 중  0개이상 N개 이하의 토핑을 중복없이 선택하여 피자를 주문할 수 있다. 따라서 여러 종류의 맞춤형 피자가 만들어지는데 이 피자들 중  1달러 당 칼로리가 가장 높을 때 이 피자를 베스트 피자라고 한다.

 

피자의 가격은 도우의 가격이 A달러이고, 고른 토핑의 개수가 K개, 토핑 당 가격이 B달러라고 하면 A + K * B 달러이다.

 

시간과 돈을 모두 절약해야 하는 앙데용꿀꿀이 입장에서는 베스트 피자를 주문해 먹을 작정이다. 앙데용꿀꿀이를 도와 베스트피자를 만들어보자. 


입력형식

첫 행에 토핑의 종류를 나타내는 N( 1 <= N <= 100)이 입력된다. 두 번째 행에 도우의 가격 A, 토핑의 가격 B( 1 <= A, B <= 1000)가 공백으로 구분되어 입력된다. 세 번째 행에 도우의 칼로리를 나타내는 정수 C(1 <= C <= 10000)가 입력된다. 네 번째 행부터 N행에 걸쳐 각 토핑의 칼로리를 나타내는 정수 Di ( 1 <= Di <= 10000)가 입력된다.

출력형식

베스트 피자의 1달러 당 열량을 출력한다. 소수 이하는 버림하고 정수로 출력한다.

입력 예

3
12 2
200
50
300
100

출력 예

37

입력 예

4
20 3
900
300
100
400
1300

출력 예

100


경기도 안양시 동안구 평촌대로 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