31993번 - AMST 스페셜 저지

문제

정점이 $n$개이고 간선이 $m$개인 단순 연결 그래프가 주어집니다. 각 간선의 가중치 함수는 일차함수 $w_i(t)=a_it+b_i$ ($-10^3 \le a_i, b_i \le 10^3$)의 꼴로 구성되며, 가중치의 값은 이 함수에 매개변수 $t$를 대입한 값입니다. 따라서, 매개변수 $t$의 값에 따라 이 그래프의 최소 스패닝 트리가 달라질 수 있습니다. 어떤 스패닝 트리의 가중치는 매개변수 $t$에 어떤 값을 대입했을 때 그 스패닝 트리에 포함된 간선의 가중치의 합이며, 최소 스패닝 트리의 가중치는 모든 스패닝 트리의 가중치 중 최솟값입니다. 정수 $S$가 주어질 때, 그래프의 최소 스패닝 트리의 가중치 합이 $S$가 되도록 하는 매개변수 $t$가 존재하는지 판단하고, 존재한다면 그러한 매개변수 $t$의 값을 구하세요.

입력

첫 번째 줄에 정점의 개수 $n$과 간선의 개수 $m$이 공백으로 구분되어 주어집니다. (2ドル \le n \le 10^5,ドル $n-1 \le m \le \min({n \choose 2},10^5)$)

그다음 줄부터 $m$개의 줄에 걸쳐 각각 간선을 나타내는 네 정수 $u_i,ドル $v_i,ドル $a_i,ドル $b_i$가 주어집니다. 이는 정점 $u_i$와 $v_i$를 연결하는 간선이 존재하며 가중치 함수는 $a_it+b_i$라는 의미입니다. (1ドル \le u_i < v_i \le n,ドル $-10^3 \le a_i, b_i \le 10^3$)

$m+2$번째 줄에는 최소 스패닝 트리의 가중치 합을 나타내는 $S$가 주어집니다. ($-10^{12} \le S \le 10^{12}$)

주어지는 그래프는 단순 연결 그래프임이 보장됩니다.

출력

최소 스패닝 트리의 가중치 합이 $S$가 되게 하는 매개변수 $t$가 존재한다면, 첫 번째 줄에 YES를 출력하고, 그러한 $t$를 두 번째 줄에 출력하세요. 각 간선의 가중치 함수에 매개변수 $t$를 대입하였을 때, 최소 스패닝 트리의 가중치 합과 $S$의 절대 오차 또는 상대 오차가 10ドル^{-5}$ 이하인 경우 정답으로 인정합니다.

그러한 $t$가 존재하지 않다면, 한 줄에 NO를 출력하세요.

제한

• 가중치 합이 $S$가 되게 하는 매개변수 $t$가 존재하지 않으면서 가중치 합과 $S$의 차가 0ドル.1$ 이하가 되게 하는 $t$가 존재하는 입력은 주어지지 않습니다.

힌트