문제 설명
세종이네 도시락 가게는 총 N명의 직원이 있다. N명의 직원들은 도시락을 만든 경력이 달라 하나의 도시락을 완성하는데 걸리는 시간이 서로 다르다. 각 직원이 하나의 도시락을 완성시키는데 걸리는 시간과 주문받은 도시락의 개수 M이 주어지면, 도시락을 모두 만드는데 걸리는 최소 시간을 구하는 프로그램을 작성해보자.
예를 들어 직원 A가 6분, 직원 B가 8분 만에 도시락을 만들 수 있다면, 5개의 도시락을 만들기 위해서는 최소 18분이 필요하다.
이때 직원 A가 3개의 도시락을, 직원 B가 2개의 도시락을 각각 만드는 경우 최소 시간이 걸린다.
예를 들어 직원 A가 6분, 직원 B가 8분 만에 도시락을 만들 수 있다면, 5개의 도시락을 만들기 위해서는 최소 18분이 필요하다.
이때 직원 A가 3개의 도시락을, 직원 B가 2개의 도시락을 각각 만드는 경우 최소 시간이 걸린다.
입력 설명
첫째 줄에는 직원의 수\((N)\)이 입력된다.\((1 \le N \le 5,000)\)
둘째 줄에는 각 직원이 도시락을 만드는데 필요한 시간\((A_i)\)이 공백으로 구분되어 입력된다.\((1 \le A_i \le 100)\)
마지막 줄에는 주문받은 도시락의 수\((M)\)가 입력된다.\((1 \le M \le 100,000,000)\)
둘째 줄에는 각 직원이 도시락을 만드는데 필요한 시간\((A_i)\)이 공백으로 구분되어 입력된다.\((1 \le A_i \le 100)\)
마지막 줄에는 주문받은 도시락의 수\((M)\)가 입력된다.\((1 \le M \le 100,000,000)\)
출력 설명
주문받은 도시락을 모두 만드는데 걸리는 최소 시간을 출력한다.
입력 예시 Copy
2
6 8
5