Russian Dolls

Time limit1sMemory limit128 MB

Summary
Given 2n dolls with height, diameter, and wall thickness, decide whether they can be split into two chains of n that each nest perfectly.
Level

Medium6 of 10

Topics
Sorting, Greedy
Solved
No attempts yet

Problem

Russian nesting dolls are hollow wooden figures. Within a set the dolls have the same shape but different sizes: the largest doll holds the second largest, which holds the third largest, and so on.

Model each doll as a cylinder of height hh, diameter dd, and wall thickness ww. Its hollow interior then has height h−2wh - 2w and diameter d−2wd - 2w. Doll BB fits inside doll AA, standing straight up, exactly when BB's outer height and outer diameter both fit within AA's hollow: that is, when BB's height is at most A.h−2 A.wA.h - 2\,A.w and BB's diameter is at most A.d−2 A.wA.d - 2\,A.w.

Boris and Natasha each own a set of nn dolls. Their two sets were mixed together into a single pile of 2n2n dolls. Decide whether the pile can be sorted back into two proper nesting sets of exactly nn dolls each — that is, whether the 2n2n dolls can be partitioned into two groups of nn so that, within each group, every doll nests inside the next-larger one.

Input

The input contains several test cases. Each test case begins with a line containing nn, the number of dolls in one set (1<n≤1001 < n \le 100). The next 2n2n lines each contain three integers hh, dd, ww — the height, diameter, and wall thickness of one doll (h,d≥2w>0h, d \ge 2w > 0). A line containing a single 00 follows the last test case.

Output

For each test case, print a single line: YES if the 2n2n dolls can be separated into two nesting sets of exactly nn dolls each, or NO otherwise.

Examples5

  1. Example 1

    Input
    3
100 100 3
97 97 3
94 94 3
91 91 3
88 88 3
85 85 3
5
100 100 1
97 97 3
98 98 1
96 96 1
94 94 1
92 92 1
90 90 1
88 88 1
86 86 1
84 84 1
0
    Expected output
    YES
YES

  2. Example 2

    Input
    2
100 100 1
98 98 1
97 97 1
95 95 1
0
    Expected output
    YES

  3. Example 3

    Input
    2
10 10 1
10 10 1
10 10 1
10 10 1
0
    Expected output
    NO

  4. Example 4

    Input
    2
20 30 2
16 26 1
18 18 1
16 16 1
0
    Expected output
    YES

  5. Example 5

    Input
    2
100 100 1
98 98 1
97 97 1
95 95 1
2
10 10 1
10 10 1
10 10 1
10 10 1
2
20 30 2
16 26 1
18 18 1
16 16 1
0
    Expected output
    YES
NO
YES