문제 번호 5060 --경로설계(Route Designing)

5060: 경로설계(Route Designing)

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 0  해결 문제 수: 0
[제출][채점상황][게시판][:]

문제 설명

농장에서 탈출한 Bessie는 아마존 강에서 여행 안내소를 차리기로 했다. 강의 양쪽에 걸쳐서 관광지들이 있고, 그 관광지 각각의 만족도가 정수로 주어져 있다.

관광지들은 강의 맞은편에 있는 다른 관광지와 연결되어 있다.(같은 편에 있는 관광지로는 이동할 수 없다.) Bessie는 관광객들을 위해서, 만족도의 합이 최대가 되도록 관광 코스를 기획하려고 하는데, 당신의 도움을 필요로 한다.

 

그런데 Bessie는 관광 코스를 같은 시간에 여러 개를 기획하고 있을 수도 있다. 그렇기 때문에 두 코스가 겹치지 않도록 하는 것이 중요하다. (a <-> x)(b <-> y)의 어떤 두 코스는 (a < b이고 y < x)이거나 (b < a이고 x < y)이거나 (a = b이고 x = y)일 때만 겹친다고 한다.

 

Bessie를 도와 최적의 코스를 구하는 프로그램을 만드시오. Bessie는 어느 곳에서나 시작점과 도착점을 정할 수 있다.

입력

Line 1 : 세 개의 정수 N, M, R(1 <= N <= 40,000, 1 <= M <= 40,000, 0 <= R <= 100,000)이 주어지는데, 각각 강의 왼쪽의 관광지 수, 오른쪽의 관광지 수, 코스의 개수를 나타낸다.

Line 2~N+1 : 강의 왼쪽에 있는 i번째 관광지의 만족도 L_i(0 <= L_i <= 40,000)가 주어진다.

Line N+2~N+M+1 : 강의 오른쪽에 있는 i번째 관광지의 만족도 R_i(0 <= R_i <= 40,000)가 주어진다.

Line N+M+2~N+M+R+1 : 두 정수 I, J(1 <= I <= N, 1 <= J <= M)가 주어진다. 강의 왼쪽에 있는 I번째 관광지와 강의 오른쪽에 있는 J번째 관광지 사이를 이동할 수 있음을 나타낸다.

출력

Line 1 : 만족도의 합의 최댓값을 출력한다.

입력예시

3 2 4
1
1
5
2
2
1 1
2 1
3 1
2 2

출력예시

8

도움말

왼쪽의 1번 관광지에서 출발하여, 오른쪽의 1번 관광지를 거쳐 왼쪽의 3번 관광지로 가는 코스가 있다. 이럴 경우, 각각의 만족도가 1, 2, 5이기 때문에, 만족도의 합은 8이고, 이는 가능한 만족도의 합의 최댓값이다.


출처

[제출][채점상황]