Immortal Jewels

Time limit8sMemory limit512 MB

Summary

Place an infinite line so it touches as many disjoint circles as possible without crossing any, where circle i is usable only if the line's distance to its surface is at most m_i.

Level: Hard8 of 10
Topics: Geometry, Brute force, Implementation, Math
Solved: No attempts yet

Problem

A nobleman fell in love with the tomboyish, brave princess of a poor country and asked for her hand in marriage. The princess set one condition: he had to bring her many jewels known as "immortal jewels." An immortal jewel is a very rare gem that can be mined only at a specific place on a certain mountain. It is also extremely fragile, so a special method is needed to extract it.

Immortal jewels are circular, and several of them lie in a two-dimensional space. To collect them, you must attract them with a special metal rod. The metal rod is a straight line of infinite length, and its thickness can be ignored. Each jewel has a magnetic force of a different strength, and a jewel sticks when the metal comes close enough to respond to that force. Specifically, let $d$ be the distance between the metal and the surface of the jewel and $m$ the strength of the jewel's magnetic force. Then

$0 \le d \le m$

means the jewel sticks to the metal. Conversely, if the rod and the jewel are farther apart than the magnetic force, the jewel cannot stick. Also, if the rod pierces the jewel even slightly, the jewel breaks and cannot stick.

Consider an example. The figure below shows an example of jewels placed in a two-dimensional space. There are jewels 1 through 6, with magnetic forces 1, 0, 1, 1, 1, 2 respectively.

Figure E-1: An example arrangement of jewels

The figure below shows an example with a metal rod placed in addition to the above. The results of attracting the jewels are also shown in the table. In this example, jewel 3 is farther away than the reach of its magnetic force, and jewel 4 is pierced by the rod, so neither can stick, but the other four all stick.

Figure E-2: An example placement of the metal rod

Jewel	Magnetic force	Distance to metal	Can it stick?
Jewel 1	1	about 0.21	yes
Jewel 2	0	0	yes
Jewel 3	1	about 5.37	no
Jewel 4	1	pierced	no
Jewel 5	1	about 0.97	yes
Jewel 6	2	about 0.53	yes

Table E-3: The sticking results

The nobleman poured in his entire fortune and desperately searched for the special metal rod. However, this metal was also very precious, so in the end he could obtain only one rod. Therefore there is only one chance to attract jewels.

You are a programmer serving a nobleman. Your job is to write a program that, for a given arrangement of jewels in the plane, finds the maximum number of jewels that can be attracted when the metal rod is placed well.

Input

The input consists of multiple datasets, and one dataset is given in the following format.

N
x1 y1 r1 m1
x2 y2 r2 m2
...
xN yN rN mN

The first line of a dataset gives the number of jewels $N$ ( $1 \le N \le 50$ ). Each of the following $N$ lines contains four integers $x_i$ , $y_i$ , $r_i$ , $m_i$ ( $-1000 \le x_i, y_i \le 1000$ , $1 \le r_i \le 100$ , $0 \le m_i \le 100$ ), giving the position, size, and magnetic force of a jewel. That is, jewel $i$ is a circle with center $(x_i, y_i)$ and radius $r_i$ , and its magnetic force is $m_i$ . Jewels do not overlap each other.

The end of the input is indicated by a line consisting of a single 0.

Output

For each dataset, output in one line the maximum number of jewels that can be attracted at once.

Examples1

Example 1

Input

Expected output