창고 이전

어떤 회사에는 1층부터 n층까지 있는 기존 창고와 1층부터 m층까지 있는 새 창고가 있다. 기존 창고의 각 층에는 물품이 몇 개씩 보관되어 있으며, 새 창고의 각 층에는 보관할 수 있는 최대 물품 수가 정해져 있다. 모든 물품의 크기는 같다고 가정한다.

모든 물품을 옮길 수 없을 수도 있으므로, 회사는 먼저 가능한 한 많은 물품을 새 창고로 옮기려고 한다. 그 수가 정해진 뒤에는 물품을 옮기는 데 드는 총비용을 최소화하려고 한다.

회사는 k명의 인부를 고용했다. 한 번의 작업은 기존 창고의 a층에서 물품 하나를 집어 새 창고의 b층으로 옮기는 것이다. 이 작업의 비용은 a+b이다. 인부는 같은 작업을 여러 번 반복할 수 있고, 모든 작업은 물품 하나씩만 옮긴다.

가능한 최대 이동 물품 수와, 그 수만큼 옮길 때의 최소 총비용을 구하라.

첫째 줄에 세 정수 n, m, k가 주어진다. (1 ≤ n, m, k ≤ 10,000)

다음 n개 줄에는 기존 창고의 1층부터 n층까지 각 층에 보관된 물품의 개수가 순서대로 주어진다.

그 다음 m개 줄에는 새 창고의 1층부터 m층까지 각 층에 보관할 수 있는 물품의 최대 개수가 순서대로 주어진다.

각 층의 물품 수와 보관 가능 수는 10,000을 넘지 않는 음이 아닌 정수이다.

첫째 줄에 두 정수 x와 y를 출력한다.

x는 옮길 수 있는 최대 물품의 개수이고, y는 x개의 물품을 옮기는 데 드는 최소 총비용이다.