최고의 피자
면접 대비시간 제한1초메모리 제한128 MB
각 토핑이 B원인 상황에서 토핑의 부분집합을 골라 총 칼로리를 총 가격으로 나눈 값이 최대가 되도록 하고, 그 몫의 정수 부분을 출력한다.
문제
상근이는 매일 저녁으로 피자를 배달시켜 먹는다. 이번 달부터는 "최고의 피자"만 주문하려고 한다. 최고의 피자란 이 가게에서 주문할 수 있는 모든 피자 중에서 1원당 열량이 가장 높은 피자를 말한다. 최고의 피자는 여러 개일 수도 있다.
피자는 도우 한 장 위에 토핑을 올려서 만든다. 가게에는 가지 토핑이 있으며, 이 중에서 원하는 만큼 골라 올릴 수 있다. 단, 같은 토핑을 두 개 이상 올릴 수는 없고, 토핑을 하나도 올리지 않아도 된다.
도우의 가격은 원이고, 토핑은 종류에 관계없이 하나당 원이다. 따라서 토핑을 개 골랐다면 피자의 가격은 원이다. 피자의 열량은 도우의 열량과 고른 토핑들의 열량을 모두 더한 값이다.
도우의 가격, 토핑 하나의 가격, 도우의 열량, 그리고 각 토핑의 열량이 주어질 때 최고의 피자의 1원당 열량을 구하여라.
입력
첫째 줄에 토핑의 종류 수 이 주어진다.
둘째 줄에 도우의 가격 와 토핑 하나의 가격 가 공백으로 구분되어 주어진다.
셋째 줄에 도우의 열량 가 주어진다.
넷째 줄부터 개의 줄에 걸쳐 각 토핑의 열량 가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 최고의 피자의 1원당 열량을 출력한다. 소수점 이하는 버리고 정수로 출력한다.
힌트
예를 들어 도우의 가격이 12원, 토핑의 가격이 2원, 도우의 열량이 200이고, 열량이 각각 50, 300, 100인 토핑 세 개가 있다고 하자. 열량이 300인 토핑과 100인 토핑을 올리면 총 열량은 이고, 가격은 원이다. 이 피자의 1원당 열량은 이며, 이 값이 가장 크므로 최고의 피자가 된다. 소수점 이하를 버려 37을 출력한다.