페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8231
서브태스크

볼리비아 셰프 3초 1024MB

문제

볼리비아 요리 레스토랑에서는 1부터 N까지 번호가 붙여진 N명의 셰프가 일하고 있습니다. 셰프 i (1 ≦ i ≦ N)는 맛이 A_i인 실판초와 맛이 B_i인 피케마초를 만들 수 있습니다.

하지만 셰프들은 고집이 세서 사이가 안 좋은 2인 조합이 M개 있습니다. 사이가 안 좋은 2인 조합의 j번째 (1 ≦ j ≦ M)는 셰프 U_j와 셰프 V_j의 2인 조합입니다.

이 레스토랑에 오는 손님은 다음과 같이 요리를 먹습니다.

1 ≦ p < q ≦ N을 만족하는 정수 p, q를 선택하고, 셰프 p와 셰프 q의 2인 조합에 요리를 만들도록 의뢰합니다. 단, 사이가 안 좋은 2인 조합에 요리를 의뢰할 수는 없습니다. 실판초와 피케마초 각각의 요리는 셰프 p와 셰프 q 중 맛이 더 높은 셰프가 만듭니다. 만약 두 셰프가 같은 맛의 요리를 만들 수 있다면, 둘 중 하나가 만듭니다. 한 명의 셰프가 두 가지 요리를 모두 만들 수 있다는 점에 유의하십시오. 손님의 만족도는 실판초의 맛과 피케마초의 맛 합계입니다. 이 레스토랑에는 1부터 Q까지 번호가 붙여진 Q명의 손님이 방문합니다.

손님 k (1 ≦ k ≦ Q)는 요리를 만들 수 있는 2인 조합 중, 만족도가 X_k번째로 높은 2인 조합에 요리를 의뢰하고자 합니다. 구체적으로 만족도를 S로 정의하며, S × N^2 + p × N + q가 X_k번째로 높은 셰프 p와 셰프 q (1 ≦ p < q ≦ N)의 2인 조합에 요리를 의뢰합니다.

레스토랑의 셰프와 손님의 정보가 주어졌을 때, 손님 k (1 ≦ k ≦ Q)의 만족도를 구하는 프로그램을 작성하세요.


입력

입력은 아래와 같은 형식으로 주어진다.

N\ M\ Q

A_1\ A_2\ …\ A_N

B_1\ B_2\ …\ B_N

U_1\ V_1

U_2\ V_2

:

U_M\ V_M

X_1\ X_2\ …\ X_Q

[제약 조건]

  • 2 ≦ N ≦ 400, 000

  • 1 ≦ A_i ≦ 10^9 (1 ≦ i ≦ N)

  • 1 ≦ B_i ≦ 10^9 (1 ≦ i ≦ N)

  • 0 ≦ M ≦ 400, 000

  • M < N(N - 1)÷2

  • 1 ≦ U_j < V_j ≦ N (1 ≦ j ≦ M)

  • (U_i, V_i) ≠ (U_j, V_j) (1 ≦ i < j ≦ M)

  • 1 ≦ Q ≦ 400, 000

  • 1 ≦ X_k ≦ 400, 000 (1 ≦ k ≦ Q)

  • X_k ≦ N(N - 1)÷2 - M (1 ≦ k ≦ Q)


출력

Q 행에 걸쳐 k 번째 행 (1 ≦ k ≦ Q)에는 손님 k의 만족도를 출력하시오.


부분문제

번호 점수 조건
#14점

N ≦ 50，M ≦ 50，Q ≦ 50，X_k ≦ 50\ (1 ≦ k ≦ Q)

#29점

B_i = 1\ (1 ≦ i ≦ N)，M = 0，Q = 1

#310점

B_i = 1\ (1 ≦ i ≦ N)，Q = 1

#45점

B_i = 1\ (1 ≦ i ≦ N)

#529점

N ≦ 100 000，M ≦ 100 000，Q = 1，X_1 = 1

#614점

N ≦ 100 000，M ≦ 100 000，Q = 1，X_1 ≦ 100 000

#718점

N ≦ 100 000，M ≦ 100 000，Q ≦ 100 000，X_k ≦ 100 000\ (1 ≦ k ≦ Q)

#811점

추가 제약 조건 없음


예제1

입력
4 2 4
2 7 3 5
4 3 4 8
1 3
2 4
1 2 3 4
출력
13
13
11
11

요리를 만들 것을 의뢰할 수 있는 셰프 두 명의 조합은 4가지가 있으며, 각각에 대한 고객의 만족도는 다음과 같습니다.

  • 셰프 1과 셰프 2를 선택했을 때, 실판초는 셰프 2가 만들고, 피케마초는 셰프 1이 만듭니다. 따라서 실판초의 맛은 7이 되고, 피케마초의 맛은 4가 됩니다. 그래서 고객의 만족도는 7 + 4 = 11이 됩니다.

  • 셰프 1과 셰프 4를 선택했을 때, 실판초는 셰프 4가 만들고, 피케마초도 셰프 4가 만듭니다. 따라서 실판초의 맛은 5가 되고, 피케마초의 맛은 8이 됩니다. 그래서 고객의 만족도는 5 + 8 = 13이 됩니다.

  • 셰프 2와 셰프 3을 선택했을 때, 실판초는 셰프 2가 만들고, 피케마초는 셰프 3이 만듭니다. 따라서 실판초의 맛은 7이 되고, 피케마초의 맛은 4가 됩니다. 그래서 고객의 만족도는 7 + 4 = 11이 됩니다.

  • 셰프 3과 셰프 4를 선택했을 때, 실판초는 셰프 4가 만들고, 피케마초는 셰프 4가 만듭니다. 따라서 실판초의 맛은 5가 되고, 피케마초의 맛은 8이 됩니다. 그래서 고객의 만족도는 5 + 8 = 13이 됩니다.

따라서 각 고객에 대해서 다음과 같은 정보가 얻어집니다.

  • 고객 1은 셰프 3과 셰프 4의 조합을 선택했습니다. 따라서 고객 1의 만족도는 13이 되었습니다.

  • 고객 2는 셰프 1과 셰프 4의 조합을 선택했습니다. 따라서 고객 2의 만족도는 13이 되었습니다.

  • 고객 3은 셰프 2와 셰프 3의 조합을 선택했습니다. 따라서 고객 3의 만족도는 11이 되었습니다.

  • 고객 4는 셰프 1과 셰프 2의 조합을 선택했습니다. 따라서 고객 4의 만족도는 11이 되었습니다.

이 입력 예시는 부분 점수 1, 7, 8의 제약을 만족합니다.


예제2

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

요리를 만들 것을 의뢰할 수 있는 셰프 두 명의 조합은 3가지가 있으며, 각각에 대한 고객의 만족도는 다음과 같습니다.

  • 셰프 1과 셰프 3을 선택했을 때, 실판초는 셰프 3이 만들고, 피케마초는 셰프 1 또는 셰프 3이 만듭니다. 따라서 실판초의 맛은 5가 되고, 피케마초의 맛은 1이 됩니다. 그래서 고객의 만족도는 5 + 1 = 6이 됩니다.

  • 셰프 1과 셰프 4를 선택했을 때, 실판초는 셰프 4가 만들고, 피케마초는 셰프 1 또는 셰프 4가 만듭니다. 따라서 실판초의 맛은 4가 되고, 피케마초의 맛은 1이 됩니다. 그래서 고객의 만족도는 4 + 1 = 5가 됩니다.

  • 셰프 3과 셰프 4를 선택했을 때, 실판초는 셰프 3이 만들고, 피케마초 셰프 3 또는 셰프 4가 만듭니다. 따라서 실판초의 맛은 5가 되고, 피케마초의 맛은 1이 됩니다. 그래서 고객의 만족도는 5 + 1 = 6이 됩니다.

따라서 고객 1에 대해 다음과 같은 정보가 얻어집니다.

  • 고객 1은 셰프 3과 셰프 4의 조합을 선택했습니다. 따라서 고객 1의 만족도는 6이 되었습니다.

이 입력 예시는 소과제 1, 3, 4, 5, 6, 7, 8의 제약을 만족합니다.


예제3

입력
5 0 4
1 2 3 4 5
5 4 3 2 1
3 9 10 1
출력
9
7
7
10

예제4

입력
13 12 10
2 28 28 60 48 77 63 92 13 71 36 91 87
85 7 64 15 55 92 66 91 83 35 49 22 61
2 9
8 13
7 11
9 11
8 12
5 12
4 7
11 12
10 12
4 11
1 5
3 8
49 21 46 13 20 41 6 33 24 7
출력
121
169
129
174
169
137
183
148
169
183

출처

JOI 2025 예선2

역링크 공식 문제집만