소 대여 서비스
면접 대비시간 제한2초메모리 제한512 MB
각 소를 우유 생산에 쓸지 임대할지 정하고, 수량과 단가가 정해진 상점에 우유를 팔아 하루 수익을 최대로 만든다.
문제
농부 존은 우유를 팔아 버는 돈만으로는 농장을 키울 수 없다고 판단했다. 그래서 부수입을 얻으려고 소를 빌려주는 서비스를 시작했다.
존에게는 소가 마리 있고, 소마다 하루에 내는 우유의 양이 정해져 있다. 농장 근처에는 가게가 개 있는데, 각 가게는 정해진 양까지만 정해진 값에 우유를 사들인다. 또 이웃 농부 명이 각자 정해진 값을 내고 소 한 마리를 하루 동안 빌리려고 한다.
존은 소마다 우유를 짤지 이웃에게 빌려줄지 둘 중 하나를 골라야 한다. 존이 하루에 벌 수 있는 최대 금액을 구하시오.
입력
첫째 줄에 , , 가 주어진다 (, , ).
다음 개 줄에는 정수 가 한 개씩 주어진다 (). 번째 소가 하루에 우유를 갤런 낸다는 뜻이다.
다음 개 줄에는 정수 와 가 주어진다 (). 번째 가게가 우유를 갤런당 센트에 최대 갤런까지 산다는 뜻이다. 한 가게에는 갤런 이상 갤런 이하의 아무 양이나 팔 수 있다.
다음 개 줄에는 정수 가 한 개씩 주어진다 (). 이웃 한 명이 소 한 마리를 하루 빌리는 값으로 센트를 낸다는 뜻이다.
출력
존이 소마다 우유를 짜거나 빌려주어 하루에 얻을 수 있는 최대 이익을 한 줄에 출력한다. 답은 32비트 정수 범위를 넘을 수 있으므로 64비트 정수형을 써야 한다.
힌트
첫 번째 예제에서 존은 1번 소와 4번 소의 우유를 짜서 13갤런을 얻는다. 10갤런짜리 주문을 모두 채워 250센트를 벌고, 남은 3갤런을 갤런당 15센트에 팔아 우유로 295센트를 번다. 나머지 소 세 마리는 각각 250센트, 80센트, 100센트를 받고 빌려주어 430센트를 더 번다. 40센트를 내겠다는 요청은 받지 않는다. 하루 이익은 모두 725센트다.