Informatica Online Judge

  프로그래밍 버그 수정 [1324 / 052C]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 12   Total Tried : 17


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

[codeforces(modify)]

Background

경곽에는 n명의 학생들이 프로그래밍 공부를 하고 있다. 이 학생들은 각자 버그를 고칠 수 있는 수준(rating)을 가지고 있다.

이번에 대형 프로젝트로 큰 프로그램을 하나 만들었다.

하지만 이 프로그램은 m개의 버그를 포함하고 있다.

각 버그는 난이도가 정해져 있다. 난이도가 높을 수록 고치기 어려운 버그이다.

이 버그를 최대한 빠른 시일 내에 모두 고치는 것이 목적이다.

어떤 학생이 어떤 버그를 고치기 위해서는 그 학생의 rating이 버그의 난이도보다 같거나 커야 한다.

즉 학생의 레이팅을 r 버그의 난이도를 d라고 할 때, r >= d 일때, 이 버그를 수정할 수 있다.

그리고 한 학생이 버그 하나를 수정하는데에는 1시간이 걸린다.

물론 여러 명의 학생들이 동시에 버그를 수정해 나갈 수 있다.

버그를 수정한 학생들에 대해서는 임금을 지불해야 한다. 만약 3명의 학생들이 버그를 수정했다면 3명의 학생에게 임금을 지불한다.

각 학생들은 자신이 받고자 하는 임금이 미리 정해져 있다.

각 정보가 주어질 때, 주어진 예산 한도 내에서 최대한 빠른 시간에 버그를 모두 수정할 수 있는 방법을 구하는 프로그램을 작성하시오.

Input

첫 번째 학생의 수, 버그의 수, 주어진 예산을 나타내는 정수 n, m, s가 공백으로 구분되어 입력된다.

두 번째 줄에 m개의 자연수 d_i가 공백으로 구분되어 입력된다. 이 값은 각 버그의 난이도를 나타내는 수이다.

세 번째 줄에 n개의 자연수 r_i가 공백으로 구분되어 입력된다. 이 값은 각 학생의 수준(rating)를 나타내는 수이다.

다음 줄에 n개의 자연수 c_i가 공백으로 구분되어 입력된다. 이 값은 각 학생들이 받고자 하는 임금을 나타낸다.

[입력값의 정의역]
1 <= n, m <= 100,000
1 <= d_i, r_i <= 1,000,000,000
0 <= s, c_i <= 1,000,000,000

Output

첫 번째 줄에 모든 버그를 주어진 예산 내에서 처리할 수 있는 최소 시간을 출력한다.

만약 일을 처리할 수 없다면 -1을 출력한다.

IO Example

입력1
3 4 10
2 3 1 2
2 1 3
4 3 6

출력1
2

입력2
3 4 5
1 3 1 2
2 1 3
5 3 6

출력2
-1

* 설명 : 입력1에서는 학생이 3명, 버그가 4개 예산이 10원이 있다.
이 때 각 버그의 난이도는 2, 3, 1, 2이고 학생의 수준은 2, 1, 3이다. 각 학생이 요구하는 임금은 4, 3, 6원이다.

이 경우에는 1번 버그를 1번 학생이, 2번 버그를 3번 학생이, 3번 버그를 다시 1번 학생이, 4번 버그를 3번 학생이 처리하면 2명의 학생이 2개씩 해결했으므로 2시간이 소요되며, 이 때 수당은 4+6원으로 10원이 든다.

따라서 주어진 예산 내에서 2시간만에 처리할 수 있다. 이보다 더 빠르게 처리할 수 있는 방법은 없다.

입력 2에서는 어떤 방법으로도 주어진 예산으로는 모든 버그를 처리할 수 없다. 따라서 -1을 출력한다.

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