여행사 상품 만들기

다현은 아마존 강을 따라 여행사를 차리기로 결정했습니다. 강의 양쪽에는 수많은 여행지가 위치해 있고, 각 여행지마다 흥미로운 정도를 나타내는 정수 값이 부여되어 있습니다.

각 여행지들은 강을 가로지르는 루트로 서로 연결되어 있습니다 (즉, 강의 같은 쪽에 있는 여행지들 사이에 연결된 루트는 없습니다). 다현은 고객들에게 흥미로운 여행을 제공하기 위해 여행 경로를 설계하고자 하며, 여러분의 도움이 필요합니다.

여행은 루트로 연결된 여행지들의 연속입니다. 고객들에게 최고의 경험을 제공하기 위해, 각 여행지의 흥미로움을 나타내는 값들의 합이 최대가 되는 루트를 찾아야 합니다.

그리고 다현은 동시에 여러 개의 여행을 운영할 수 있습니다. 따라서 여행 경로들이 서로 교차하지 않게 하는 것이 중요합니다. 두 개의 루트가 (a <-> x) 와 (b <-> y)로 연결되어 있다면, (a < b 그리고 y < x) 또는 (b < a 그리고 x < y) 또는 (a = b 그리고 x = y) 인 경우에만 교차합니다.

다현을 도와 그녀의 여행사를 위해 최고의 여행을 찾아주세요. 다현은 아마존 강의 양쪽 중 어느 곳에서든 시작하고 끝낼 수 있습니다.

• 첫 번째 줄 : 세 개의 공백으로 구분된 정수 N (1 <= N <= 40,000), M (1 <= M <= 40,000), 그리고 R (0 <= R <= 100,000)로 각각 강 왼쪽에 있는 여행지의 수, 강 오른쪽에 있는 여행지의 수, 그리고 루트의 수를 나타낸다.
• 두 번째 줄..N+1 번째 줄 : (i+1)번째 줄은 단일 정수, L_i (0 <= L_i <= 40,000)를 갖으며, 이는 강 왼쪽에 있는 i번째 여행지의 가치를 나타낸다.
• N+2 번째 줄..N+M+1 번째 줄 : (i+N+1)번째 줄은 단일 정수, R_i (0 <= R_i <= 40,000)를 갖으며, 이는 강 오른쪽에 있는 i번째 여행지의 가치를 나타낸다.
• N+M+2 번째 줄..N+M+R+1 번째 줄 : 각 줄은 두 개의 공백으로 구분된 정수 I (1 <= I <= N) 와 J (1 <= J <= M)을 포함하며, 이는 강 왼쪽에 있는 여행지 I와 강 오른쪽에 있는 여행지 J 사이에 양방향 루트가 존재함을 나타낸다.

• 첫 번째 줄 : 여행에서 가능한 흥미로움 값들의 최대 합을 나타내는 단일 정수.