단체 항공권 구매 계획

문제

여행 담당자가 같은 항공편을 이용할 N명의 항공권을 구매하려 한다. 판매 창구에서는 개별 항공권과 묶음 항공권을 판매한다. 개별 항공권 한 장으로 한 명이 탑승할 수 있으며 가격은 Q원이다. 묶음 항공권 하나에는 정확히 K장의 항공권이 들어 있으며 가격은 P원이다. 묶음을 나누어 구매할 수는 없지만, 구매한 항공권 중 일부를 사용하지 않는 것은 허용한다. 묶음 항공권을 하나 이상 구매하면 전체 구매에 대해 처리 비용 F원이 한 번 추가된다. 묶음을 여러 개 구매하더라도 처리 비용은 한 번만 낸다. 개별 항공권만 구매하면 처리 비용은 발생하지 않는다. 모든 가격은 구매 수량과 관계없이 일정하며, 다른 할인이나 추가 비용은 없다. 구매 계획은 묶음 개수 x로 정한다. x는 0 이상, N을 K로 나눈 값을 올림한 수 이하의 정수여야 한다. 묶음에서 얻은 항공권이 N장보다 적으면 부족한 장수만큼 개별 항공권을 구매한다. 묶음에서 얻은 항공권이 N장 이상이면 개별 항공권은 구매하지 않는다. 따라서 각 x에 대응하는 구매 계획은 하나로 결정된다. 담당자는 허용된 모든 구매 계획 중 총비용이 가장 작은 계획을 선택한다. 총비용이 같은 계획이 여러 개라면 묶음 개수가 가장 작은 계획을 선택한다. 사용하지 않은 항공권은 환불하거나 다른 사람에게 판매할 수 없으며, 그 장수는 동점 처리에 영향을 주지 않는다. 개별 항공권만으로도 모든 사람의 항공권을 마련할 수 있으므로 가능한 계획은 항상 존재한다. 선택한 계획의 총비용과 묶음 개수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, K, P, Q, F가 공백으로 구분되어 주어진다.
1 ≤ N ≤ 100,000, 2 ≤ K ≤ 10, 1 ≤ P, Q ≤ 1,000,000, 0 ≤ F ≤ 1,000,000이다. 모든 금액의 단위는 원이다.

출력

선택한 계획의 총비용과 묶음 개수를 순서대로 한 줄에 공백으로 구분하여 출력한다. 두 값 모두 정수로 출력한다.

9 4 270 80 30

650 2

1 3 200 70 50

70 0

8 4 400 100 0

800 0

출처: Devin.KR 자체 제작