Džumbus
시간 제한1초메모리 제한512 MB
각 친구의 음주 임계값이 주어진 숲에서, 총 음료량 S를 공급하는 Q개의 질의마다 해답을 교환하게 되는 최대 인원을 구한다.
문제
Marin은 좋은 사람이라서 경쟁 프로그래머인 N명의 친구를 위해 Q번의 파티를 열 것이다. 파티에서 제공되는 유일한 음료는 džumbus로, 콜라와 생강 주스의 혼합물이다.
Marin은 각 친구가 긴장을 풀기 위해 마셔야 하는 džumbus의 양을 알고 있다. 또한 친구들 사이에 M쌍의 관계가 있어서, 두 사람이 모두 긴장을 풀면 과거 COCI 문제의 풀이를 교환하기 시작한다는 것도 알고 있다(공개된 에디토리얼이 없기 때문이다). 사람 A가 자신의 풀이를 사람 B에게 공유하면, 사람 B는 같은 방식으로 그 풀이를 공유할지 결정할 수 있지만, M쌍은 교환 순서에 관계없이 그 파티 중에 풀이가 사람 A에게 다시 돌아오는 것이 불가능하도록 형성되어 있다.
Marin은 각 파티마다 다른 양의 džumbus를 준비했다. 각 파티에서 그는 그 파티에서 적어도 한 번 다른 사람과 풀이를 교환할 사람의 수가 최대가 되도록 음료를 분배할 것이다.
여러분의 과제는 Q번의 파티 각각에 대해 풀이를 교환할 사람의 수를 구하는 것이다.
입력
첫 번째 줄에는 문제 설명의 정수 N과 M이 주어진다.
두 번째 줄에는 Marin의 친구들이 긴장을 풀기 위해 필요한 džumbus의 양 Di가 친구 번호 1부터 친구 번호 N까지의 순서로 N개 주어진다. 각 값은 공백으로 구분된다.
다음 M개 줄의 i번째 줄에는 문제 설명의 친구 쌍을 나타내는 두 정수 Ai와 Bi (Ai ≠ Bi)가 주어진다.
다음 줄에는 문제 설명의 정수 Q가 주어진다.
다음 Q개 줄에는 i번째 파티에서 제공될 džumbus의 총량을 나타내는 정수 Si가 하나씩 주어진다.
출력
Q번의 파티 각각에 대해 풀이를 교환할 사람의 수를 출력한다. 각 파티의 답은 한 줄에 하나씩 출력해야 한다. 파티들은 서로 독립적이다.
제한
모든 부분 문제에서 0 ≤ M < N ≤ 1000, 1 ≤ Q ≤ 2 · 105, 1 ≤ Di ≤ 109, 1 ≤ Si ≤ 109이다.
예제 1
입력:
1 0
1000
1
1000
기대 출력:
0
예제 2
입력:
3 2
1 2 3
1 2
1 3
3
2
3
5
기대 출력:
0
2
2
예제 3
입력:
14 13
2 3 4 19 20 21 5 22 6 7 23 8 10 14
1 2
1 3
1 4
2 5
2 6
3 7
3 8
3 9
4 10
8 11
10 13
10 12
12 14
3
45
44
23
기대 출력:
8
7
5