최고의 피자

면접 대비

시간 제한1초메모리 제한128 MB

요약
각 토핑이 B원인 상황에서 토핑의 부분집합을 골라 총 칼로리를 총 가격으로 나눈 값이 최대가 되도록 하고, 그 몫의 정수 부분을 출력한다.
난이도

보통10점 중 4점

유형
그리디, 정렬, 완전 탐색, 수학
정답자
아직 제출이 없습니다

문제

상근이는 매일 저녁으로 피자를 배달시켜 먹는다. 이번 달부터는 "최고의 피자"만 주문하려고 한다. 최고의 피자란 이 가게에서 주문할 수 있는 모든 피자 중에서 1원당 열량이 가장 높은 피자를 말한다. 최고의 피자는 여러 개일 수도 있다.

피자는 도우 한 장 위에 토핑을 올려서 만든다. 가게에는 NN가지 토핑이 있으며, 이 중에서 원하는 만큼 골라 올릴 수 있다. 단, 같은 토핑을 두 개 이상 올릴 수는 없고, 토핑을 하나도 올리지 않아도 된다.

도우의 가격은 AA원이고, 토핑은 종류에 관계없이 하나당 BB원이다. 따라서 토핑을 kk개 (0≤k≤N)(0 \le k \le N) 골랐다면 피자의 가격은 A+B×kA + B \times k원이다. 피자의 열량은 도우의 열량과 고른 토핑들의 열량을 모두 더한 값이다.

도우의 가격, 토핑 하나의 가격, 도우의 열량, 그리고 각 토핑의 열량이 주어질 때 최고의 피자의 1원당 열량을 구하여라.

입력

첫째 줄에 토핑의 종류 수 NN (1≤N≤100)(1 \le N \le 100)이 주어진다.

둘째 줄에 도우의 가격 AA와 토핑 하나의 가격 BB가 공백으로 구분되어 주어진다. (1≤A,B≤1000)(1 \le A, B \le 1000)

셋째 줄에 도우의 열량 CC가 주어진다. (1≤C≤10000)(1 \le C \le 10000)

넷째 줄부터 NN개의 줄에 걸쳐 각 토핑의 열량 DiD_i가 한 줄에 하나씩 주어진다. (1≤Di≤10000)(1 \le D_i \le 10000)

출력

첫째 줄에 최고의 피자의 1원당 열량을 출력한다. 소수점 이하는 버리고 정수로 출력한다.

힌트

예를 들어 도우의 가격이 12원, 토핑의 가격이 2원, 도우의 열량이 200이고, 열량이 각각 50, 300, 100인 토핑 세 개가 있다고 하자. 열량이 300인 토핑과 100인 토핑을 올리면 총 열량은 200+300+100=600200 + 300 + 100 = 600이고, 가격은 12+2×2=1612 + 2 \times 2 = 16원이다. 이 피자의 1원당 열량은 600/16=37.5600 / 16 = 37.5이며, 이 값이 가장 크므로 최고의 피자가 된다. 소수점 이하를 버려 37을 출력한다.

예제2

  1. 예제 1

    입력
    3
    12 2
    200
    50
    300
    100
    
    예상 출력
    37
    
  2. 예제 2

    입력
    4
    20 3
    900
    300
    100
    400
    1300
    
    예상 출력
    100