32620번 - 점령

문제

양방향 그래프와 시작 노드 $r$이 주어진다. 그래프의 노드는 1,2,ドル\dots ,N$의 번호가 붙어 있다. $i$번 노드를 점령하려면, $A_i$ 이상의 기력을 보유하고 있으면서 $i$번 노드의 이웃 노드를 하나 이상 점령하고 있어야 한다. 또한, $i$번 노드를 점령하면 보유한 기력이 $B_i$만큼 증가한다. 점령한다고 보유한 기력이 $A_i$만큼 감소하는 것은 아니다. 얻을 수 있는 최대 기력이 얼마인지 구하여라. 시작 노드는 이미 점령된 상태이며, 따라서 시작 상태에서 보유한 기력은 시작 노드를 점령할 때 얻을 수 있는 기력인 $B_r$이다.

입력

첫 번째 줄에 노드의 개수 $N,ドル 간선의 개수 $M,ドル 시작 노드 $r$이 공백으로 구분되어 주어진다. (1ドル \le N \le 500,000円$; 0ドル\le M \le 1,000円,000円$; 1ドル\le r \le N$)

두 번째 줄에 각 노드를 점령하는 데 필요한 기력 $A_1, A_2, \dots ,A_N$이 공백을 사이에 두고 주어진다. (0ドル\le A_i \le 10^9$; $A_r=0$)

세 번째 줄에 각 노드를 점령했을 때 얻을 수 있는 기력 $B_1, B_2, \dots ,B_N$이 공백을 사이에 두고 주어진다. (0ドル\le B_i \le 10^9$)

네 번째 줄부터 $M$개의 줄에 걸쳐 $M$개의 간선에 대한 정보를 나타내는 두 정수 $u,ドル $v$가 공백으로 구분되어 주어진다. 이는 $u$와 $v$가 이웃임을 의미한다. (1ドル\le u,v \le N$; $u \ne v$)

출력

얻을 수 있는 최대 기력을 출력한다.

제한

힌트