31877번 - EDF

문제

민구는 이번 년도에 일이 너무 많아서 $N$개의 작업이 쌓여있으며, 시간이 흐르면서 최대 $M$개의 작업이 추가된다.

기존에 있던 작업은 작업에 필요한 시간 $t_i$와 마감 시각 $d_i$가 주어지고, 추가되는 작업은 추가되는 시각 $w_j,ドル 작업에 필요한 시간 $t_j,ドル 마감 시각 $d_j$가 주어진다.

민구는 각 작업에 대해서 마감 시각이 가장 가까운 작업부터 시작하는데, 작업 도중 새로 추가된 작업의 마감 시각이 더 이를 경우 새로 추가된 작업을 한다. 기존에 하던 작업은 나중에 다시 이어서 할 수 있도록 작업에 필요한 시간이 작업을 했던 시간만큼 차감된다.

예를 들어, 작업에 필요한 시간이 20분인 작업을 15분 동안 하다가 다른 작업으로 교체했을 경우, 기존에 하던 작업은 추후 5분만 추가적으로 작업을 하면 완료할 수 있다.

마감 시각이 같은 작업들에 대해서는 작업에 필요한 시간이 더 적게 남아있는 작업을 먼저 한다.

위 과정을 통해 총 $N + M$개의 작업에 대해서 민구가 모든 작업을 완료할 수 있는지 알려주자.

민구는 한 가지 일에 집중하는 스타일이기에 한 번에 하나의 작업밖에 못한다. 또한 $N + M$개의 작업을 모두 완료할 때까지 작업을 한다.

현재 시각은 0ドル$초이다.

입력

첫 번째 줄에 작업의 개수 $N$이 주어진다. $(1 \le N \le 10^5)$

다음 $N$개의 줄에 각 작업의 걸리는 시간 $t_i,ドル 마감 시각 $d_i$이 주어진다. $(0 \le t_i \le 10^9; 1 \le d_i \le 10^9; t_i \le d_i)$

이후 $N + 2$번째 줄에 작업 도중 추가될 작업의 개수 $M$이 주어진다. $(1 \le M \le N)$

다음 $M$개의 줄에 각 작업의 추가되는 시각 $w_j,ドル 걸리는 시간 $t_j,ドル 마감 시각 $d_j$가 주어진다. $(0 \le t_j \le 10^9; 1 \le w_j, d_j \le 10^9; w_j + t_j \le d_j)$

출력

첫 번째 줄에 민구가 작업을 모두 완료하지 못 한다면 NO를 출력하고, 작업을 모두 완료할 수 있다면 YES를 출력한다.

만약 작업을 모두 완료할 수 있다면, 두 번째 줄에 모든 작업을 완료하는 최소 시각을 출력한다.

제한

힌트