The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Round 125 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

data structures

sortings

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Gripping Story

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputOne day Qwerty the Ranger witnessed two transport ships collide with each other. As a result, all contents of their cargo holds scattered around the space. And now Qwerty wants to pick as many lost items as possible to sell them later.

The thing is, both ships had lots of new gravitational grippers, transported to sale. A gripper is a device that can be installed on a spaceship and than draw items in space to itself ("grip") and transport them to the ship's cargo hold.

Overall the crashed ships lost *n* gravitational grippers: the *i*-th gripper is located at a point with coordinates (*x*_{i}, *y*_{i}). Each gripper has two features — *p*_{i} (the power) and *r*_{i} (the action radius) and can grip any items with mass of no more than *p*_{i} at distance no more than *r*_{i}. A gripper itself is an item, too and it has its mass of *m*_{i}.

Qwerty's ship is located at point (*x*, *y*) and has an old magnetic gripper installed, its characteristics are *p* and *r*. There are no other grippers in the ship's cargo holds.

Find the largest number of grippers Qwerty can get hold of. As he picks the items, he can arbitrarily install any gripper in the cargo hold of the ship, including the gripper he has just picked. At any moment of time the ship can have only one active gripper installed. We consider all items and the Qwerty's ship immobile when the ranger picks the items, except for when the gripper moves an item — then the item moves to the cargo holds and the ship still remains immobile. We can assume that the ship's cargo holds have enough room for all grippers. Qwerty can use any gripper he finds or the initial gripper an arbitrary number of times.

Input

The first line contains five integers *x*, *y*, *p*, *r* and *n* ( - 10^{9} ≤ *x*, *y* ≤ 10^{9}, 1 ≤ *p*, *r* ≤ 10^{9}, 1 ≤ *n* ≤ 250000) — the ship's initial position, the initial gripper's features and the number of grippers that got into the space during the collision.

Next *n* lines contain the grippers' descriptions: the *i*-th line contains five integers *x*_{i}, *y*_{i}, *m*_{i}, *p*_{i}, *r*_{i} ( - 10^{9} ≤ *x*_{i}, *y*_{i} ≤ 10^{9}, 1 ≤ *m*_{i}, *p*_{i}, *r*_{i} ≤ 10^{9}) — the *i*-th gripper's coordinates and features.

It is guaranteed that all grippers are located at different points. No gripper is located at the same point with Qwerty's ship.

Output

Print a single number — the maximum number of grippers Qwerty can draw to his ship. You do not need to count the initial old magnet gripper.

Examples

Input

0 0 5 10 5

5 4 7 11 5

-7 1 4 7 8

0 2 13 5 6

2 -3 9 3 4

13 5 1 9 9

Output

3

Note

In the first sample you should get the second gripper, then use the second gripper to get the first one, then use the first gripper to get the fourth one. You cannot get neither the third gripper as it is too heavy, nor the fifth one as it is too far away.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/29/2023 09:20:20 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|