The young girl Xiao-Xian is a very cute girl. With the progress of technology, people in the fantasy land have also started using mobile phones. Xiao-Xian discovered that the sun-flower field she visits has no Wi-Fi. She felt very sad, so she asked around and found out that everyone dislikes this place because there is no Wi-Fi, and mobile data is also expensive.

What should she do? Xiao-Xian decided to set up some Wi-Fi access points as soon as possible so that everyone can surf the internet happily in the sun-flower field.

We can approximate the sun-flower field as a region in the $y \in [0, R]$ strip, where $x \in (-\infty, +\infty)$ (that is, an infinitely long rectangular region extending along the $x$-axis).

There are $n$ points of interest in the sun-flower field that tourists often visit. Xiao-Xian wants to cover as many of these points as possible with Wi-Fi so that the tourists will be satisfied.

Zi-Zi said she could help set up Wi-Fi routers. Currently, the routers have a fixed coverage radius of $R$. Zi-Zi scanned the map and found that outside the sun-flower field, there are $m$ potential locations where she can set up routers. If you set up a router at point $p$, then for any point $q$, if the Euclidean distance between $p$ and $q$ is less than or equal to $R$, then point $q$ will be covered by Wi-Fi.

At the same time, Zi-Zi mentioned that the difficulty of setting up varies by location, so the costs are different, with the $i$-th location costing $c_i$.

Now, Xiao-Xian wants to cover as many points of interest as possible. Under this premise, she also wants to save as much money as possible. Can you help her?

Input

The first line contains three integers $n, m, R$, satisfying $1 \le R \le 10^8$, representing the number of points of interest, the number of potential router locations, and the width of the sun-flower field.

Next $n$ lines, each containing two integers $x, y$, satisfying $-10^8 \le x \le 10^8, 0 \le y \le R$, representing a point of interest. No two points of interest coincide.

Next $m$ lines, each containing three integers $x, y, c$, satisfying $-10^9 \le x \le 10^9, -10^8 < y < 0$ or $R < y < 10^8$, and $0 \le c \le 10^4$. These represent the location and cost of a potential router. No two router locations coincide.

Output

The first line outputs the maximum number of points of interest covered.

The second line outputs the minimum cost required to cover that maximum number of points.

Constraints

• For 10% of the data, $n, m \le 20$.
• For another 30% of the data, $n, m \le 100$, and all router locations have $y > R$.
• For the remaining 60% of the data, $n, m \le 100$.

Examples

Input 1

10 10 10000
6743 2963
3505 1986
3565 7235
1735 5522
16877 5597
11621 6
3100 8243
1750 6173
5709 7671
7915 3915
14339 -438 3075
4278 15210 8371
13996 19000 6750
17049 -4969 7788
737 16339 2934
904 14023 2322
8982 14759 4311
13102 11458 5554
4135 12183 576
5087 -2459 6787

Output 1

10
10438