Informatica Online Judge

  개미 이사 [1241 / 04D9]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 21   Total Tried : 233


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

경곽이는 개미에 대해서 연구를 하고 있다.

개미는 땅에 굴을 파고 집을 짖고 산다.

이번에 A영역의 개미 집의 모든 먹이와 애벌래들을 B영역으로 이사를 하려고 한다.

A영역의 개미굴은 깊이가 n센치미터이고 각 1센치미터 마다 창고가 위치한다.

B영역의 개미굴은 깊이가 m센치미터이고 각 1센치미터 마다 창고가 위치한다.

k마리의 일개미들 이사 작업을 진행하고 있다.

한 마리의 일개미가 A영역의 지하 x센치미터에 위치하는 창고에서 B영역의 지하 y센치미터에 위치하는 창고로 짐을 1개 옮기는데 드는 노동력은 x+y 이다.

경곽이는 A영역의 각 창고들에서 옮겨야 하는 짐의 수가 주어지고, B영역의 각 창고의 용량이 주어질 때, k마리의 일개미들이 최대한 많은 짐을 옮기기 위해서 드는 최소 노동력을 알고싶어한다.

이를 도와주는 프로그램을 작성하시오.

Input

첫 번째 줄에 A영역의 깊이 a, B영역의 깊이 b, 일개미의 수 k가 입력으로 주어진다.

두 번째 줄에 A영역의 각 1센치미터 깊이별로 위치하는 창고에 있는 옮길 짐의 수가 공백으로 구분되어 입력된다.

세 번째 줄에 B영역의 각 1센치미터 깊이별로 위치하는 창고에 수용할 수 있는 짐의 수를 나타내는 정수들이 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= n, m, k <= 10,000

Output

k마리의 일개미들이 옮길 수 있는 최대 짐의 양과 이 때 드는 최소 노동력을 공백으로 구분하여 출력한다.

IO Example

입력
1 2 10
5
1 1

출력
2 5

* 설명 : 개미굴 A의 깊이는 1cm이고 개미굴 B의 깊이는 2cm이며, 일개미는 10마리가 있다.
그리고 A영역에 1cm에 위치하는 창고에 5개의 짐이 있고, B의 지하 1cm, 2cm에 각각 1개의 짐을 보관할 수 있는 창고가 있으므로,
두 마리의 일개미가 각각

A의 지하 1cm - > B의 지하 1cm로 옮긴다. (노동력 2)
A 지하 1cm -> B지하 2cm 로 옮긴다. (노동력 3)

따라서 모두 2개의 짐을 옮길 수 있으며 드는 최소 노동력은 5이다. 이보다 더 적은 노동력으로 옮길 수 있는 방법은 없다.

따라서 짐은 최대 1개 옮길 수 있고 이 때 드는 최소 노동력은 2이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]