405376: GYM101917 I Water in BeagleTown

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Water in BeagleTowntime limit per test2.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There have been some really hot days in BeagleTown, so beagles have been training themselves to get enough water as fast as possible with the following exercise:

Googles places the water bowls with $$$w$$$ liters of water at specific locations. The beagles get to each of their starting positions and then they start the exercise: trying to drink 1 liter of water before $$$s$$$ seconds have passed.

Beagles are very good at their trainning, but they have a little problem: They are bad at designing the exercises. LH is out of town, so it is you task to make sure that the exercise they prepared is solvable.

Input

The first line of the input contain integers $$$n$$$, $$$m$$$ and $$$s$$$ ($$$1 \le n, m \le 2 000$$$) ($$$1 \le s \le 10^{10}$$$)

The next $$$n$$$ lines contain 2 integers each: $$$x_i$$$, $$$y_i$$$; starting position of the $$$i$$$ beagle. ($$$-10^9 \le x_i, y_i \le 10^9$$$)

The next $$$m$$$ lines contain 3 integers each: $$$x_j$$$, $$$y_j$$$, $$$w_j$$$; position and liters of water of the $$$j$$$ water bowl. ($$$-10^9 \le x_j, y_j \le 10^9$$$) ($$$1 \le w_j \le 100$$$)

Output

Output the expected answer (without quotation marks):

"YES" if it is possible or

"NO" if it is not possible.

ExamplesInput
3 3 20
-10 6
-4 9
-2 2
8 -4 4
4 0 100
-10 9 41
Output
YES
Input
3 3 15
3 -2
3 -1
-9 -8
-6 -4 34
5 4 11
-8 2 15
Output
NO
Note

Beagles from BeagleTown love eating pears, but they can get only 1 pear per day.

Beagles move 1 unit per second.

Beagles drink 1 liter of water in 10 seconds.

Beagles organize themselves very well, if the exercise has a solution, 100% of the times they will find it.

Source/Category

加入题单

上一题 下一题 算法标签: