Wireless

Interview

Time limit1sMemory limit128 MB

Summary

Given K circles with integer centers and integer radii on a grid of intersections, compute the maximum total bitrate sum any intersection receives and how many intersections achieve it.

Level: Medium7 of 10
Topics: Geometry, Implementation, Brute force, Sorting
Solved: No attempts yet

Problem

Bob is sitting at home with his computer. He would like to experience more social interaction, so he is planning a trip to a coffee shop with his computer.

In Bob's city there is one coffee shop at every intersection of streets. The city has $M$ streets that run east and west ( $1 \le M \le 30000$ ) and $N$ streets that run north and south ( $1 \le N \le 1000$ ). The distance between consecutive parallel streets is exactly 1 metre (it is a very compact city).

Inside $K$ of the coffee shops ( $1 \le K \le 1000$ ) there is a wireless network station. Each station has a bitrate $B$ ( $1 \le B \le 1000$ ) and can reach up to $R$ metres ( $1 \le R \le 30000$ ) from its coffee shop. In other words, a station covers a circle of radius $R$ centred at its coffee shop. Someone exactly at distance $R$ can use the network, but someone at a distance greater than $R$ cannot.

Each coffee shop holds at most one wireless station, yet several networks may be usable from a single coffee shop when stations at nearby shops reach it.

Bob's computer has a special device that can combine and use the bitrates of every wireless network it can connect to.

Bob would like to know the maximum bitrate he can obtain and how many coffee shops offer that maximum.

Input

The first line contains the integer $M$ , the number of east-west streets. The second line contains the integer $N$ , the number of north-south streets. The third line contains the integer $K$ , the number of coffee shops that have a wireless network. Each of the next $K$ lines contains four integers. The first integer $x$ is the north-south street the coffee shop is on, with $1 \le x \le N$ . The second integer $y$ is the east-west street the coffee shop is on, with $1 \le y \le M$ . The third integer $R$ is the radius of that coffee shop's wireless network. The fourth integer $B$ is the bitrate of that coffee shop's wireless network.

Output

The output is two lines. The first line is the integer giving the maximum bitrate obtainable over all coffee shops (intersections). The second line is the number of coffee shops at which this maximum bitrate can be obtained.

Hint

In the figure below, the five coffee shops (intersections) marked with a dark circle all have total bitrates of 12.

Examples5

Example 1
Input
```
3
5
3
1 3 2 5
3 1 2 7
5 1 1 5
```
Expected output
```
12
5
```
Example 2
Input
```
1
1
1
1 1 1 10
```
Expected output
```
10
1
```
Example 3
Input
```
1
1
2
1 1 1 3
1 1 1 4
```
Expected output
```
7
1
```
Example 4
Input
```
1
3
1
2 1 1 5
```
Expected output
```
5
3
```
Example 5
Input
```
1
5
2
2 1 1 3
4 1 1 4
```
Expected output
```
7
1
```