시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 11 4 4 36.364%

문제

n(1≤n≤10,000)층짜리의 창고를 가지고 있는 한 회사가 있다. 이 회사에서는 이번에 새로 m(1≤m≤10,000)층짜리의 창고를 하나 마련하여 새 창고로 이전을 하려 한다.

기존의 창고에서 보관 중이던 물품들을 모두 새 창고로 옮길 수 있다면 좋겠지만, 새로운 창고가 더 클 수도, 작을 수도 있다. 이러한 경우에는 우선 최대한 많은 물품을 옮기려고 한다. 편의상 모든 물품들은 같은 크기라고 가정한다. 이러한 물품들이 기존의 창고의 각 층에 몇 개씩 보관되어 있었는지에 대한 정보가 주어지고, 새로운 창고의 각 층에 최대 몇 개씩 보관할 수 있는지에 대한 정보도 주어진다.

한편, 건물의 구조적 특징 때문에 물품을 옮길 때에는 사람이 직접 옮기는 방식을 이용하여야 한다. 이를 위해서 회사에서는 k(1≤k≤10,000)명의 인부를 고용하였다. 각 인부는 우선 기존 창고의 a번 층으로 이동하고, 한 개의 물품을 들어 올린 다음, 이를 새로운 창고의 b번 층으로 옮기게 된다. 창고를 오르고 내려올 때에는 층수에 비례하는 시간이 들기 때문에, 이러한 작업을 완료하는 데에는 총 a+b 만큼의 시간이 든다. 각각의 인부는 이러한 작업을 여러 번 반복하게 되고, 회사에서는 각 인부들에게 그 인부가 일 하는데 든 총 시간만큼의 비용을 지불하기로 하였다. 모든 인부들은 오래 일을 하여 그만큼 많은 돈을 받으려고 하기 때문에, 항상 물품은 한 개씩만 움직인다고 하자.

회사 측에서는 우선 최대한 많은 물품을 옮기기를 원한다. 그 다음으로는, 이 물품들을 옮기는 데 드는 비용을 최소로 하려 한다. 이를 도와주는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 n, m, k가 주어진다. 다음 줄에는 n개의 정수로 기존 창고의 각 층에 보관되어 있는 물품의 개수가 1층부터 n층의 순서로 주어진다. 다음 줄에는 m개의 정수로 새 창고의 각 층에 보관할 수 있는 물품의 개수가 1층부터 m층의 순서로 주어진다. 각 층에 보관되어 있는, 그리고 보관할 수 있는 물품의 개수는 10,000개를 넘지 않는다.

출력

첫째 줄에 두 정수 x, y를 출력한다. x는 옮길 수 있는 최대 물품의 개수이고, y는 이 때 드는 비용의 최소값이다.

예제 입력

1 1 1
1
1

예제 출력

1 2

힌트