# instance by G2
# solution = 0010111101110100110111111100101110001111111111000001001110011000100000011100110000000011100100011111
100 600 3
-78 2 89 
-39 7 80 
57 84 83 
10 18 -77 
-30 17 -33 
49 -91 93 
-17 24 19 
-58 -82 57 
-9 67 -57 
5 48 -94 
28 86 29 
87 -73 -25 
-80 -7 -30 
61 13 -78 
-11 39 54 
-90 -31 71 
-79 5 -88 
22 -84 -73 
-42 -35 -29 
-54 -41 79 
-57 74 51 
-4 64 -60 
-98 -30 12 
18 29 -58 
-83 -26 89 
-63 -54 20 
70 56 -89 
-18 -90 -78 
35 84 14 
60 -83 -22 
41 -94 -74 
34 25 81 
23 39 34 
-45 66 37 
81 60 93 
18 93 -74 
65 -54 41 
-100 -82 36 
22 -26 54 
74 -8 100 
90 11 -43 
-65 100 -90 
-29 -1 -23 
-29 -50 44 
18 -34 -84 
48 11 -92 
56 38 -90 
62 8 90 
76 22 66 
11 -76 14 
-85 68 -11 
-32 50 -51 
78 -73 -89 
-73 14 -13 
-57 -34 53 
-32 -52 -75 
-37 78 -12 
99 -76 22 
-70 31 -97 
20 -49 71 
44 -78 -80 
93 -97 20 
40 90 -45 
-1 13 12 
-57 -45 -83 
-94 -63 -42 
-81 86 -38 
-66 31 82 
-13 -89 -80 
52 -46 -10 
-2 -96 100 
24 -6 39 
77 -4 33 
-34 -87 8 
64 -72 -69 
-3 98 82 
-8 -16 -85 
-80 -20 84 
23 -37 71 
37 48 -20 
-79 9 -59 
-75 -5 -9 
28 -91 -50 
-69 -82 83 
-33 21 -11 
-72 25 -2 
-45 -30 -29 
11 -18 36 
29 83 51 
-39 7 27 
-80 -53 13 
-39 -50 70 
-61 -9 -57 
76 5 11 
-45 77 -7 
19 -66 -65 
-14 -67 48 
52 -44 -65 
-71 -67 5 
47 1 43 
-81 88 -19 
-76 75 -56 
-10 83 -27 
-67 -81 16 
57 -85 21 
74 76 78 
40 -20 -25 
16 -66 -22 
-30 -25 96 
-53 33 24 
59 89 -45 
-66 24 33 
-43 32 21 
-28 99 88 
-16 -13 70 
-92 -50 2 
21 54 9 
-64 -75 -97 
54 95 -35 
25 11 39 
-36 -73 31 
27 52 90 
-29 79 32 
46 -77 -23 
34 -81 -14 
-63 18 -10 
-98 -74 25 
32 58 -44 
40 82 -11 
45 -89 -40 
-16 -86 4 
-50 -99 -42 
-85 7 98 
-11 -65 42 
43 -31 -82 
-49 48 85 
-15 41 -43 
30 11 -52 
-83 32 -59 
-3 -79 -43 
50 -14 72 
-60 -69 72 
-38 -9 72 
-58 -6 66 
39 -11 -90 
-100 12 -22 
-57 27 21 
-3 17 53 
98 -26 -77 
-92 -22 -34 
76 89 46 
-77 17 -71 
63 60 22 
-80 71 95 
-33 100 -36 
42 -84 44 
-88 58 -83 
18 -11 73 
21 74 33 
87 -21 -66 
57 81 93 
-76 23 -21 
13 86 39 
-81 -3 67 
-89 -70 6 
72 41 27 
-100 -98 65 
38 -88 70 
50 24 -10 
-84 48 -38 
39 19 -82 
100 -44 25 
-2 -60 50 
60 -50 -20 
12 60 -10 
72 -92 -10 
-98 -96 -9 
48 -60 -90 
-31 23 22 
76 -69 74 
56 -32 21 
17 -66 -10 
41 -74 93 
26 20 -28 
-57 -27 96 
40 -34 -37 
-7 30 -4 
96 68 -80 
-83 67 93 
-19 85 -8 
-60 -84 93 
-6 45 94 
94 -28 -44 
-83 -97 -65 
-93 45 88 
-75 -78 -67 
-34 66 44 
-53 15 36 
-90 -17 -74 
75 -5 42 
-83 -97 49 
4 -48 -93 
-89 27 72 
3 52 -36 
10 -70 -94 
100 -74 -50 
-37 92 -8 
-87 84 88 
20 -61 78 
-79 -25 24 
-67 -53 -69 
-4 -81 -29 
90 -94 -25 
91 -35 -51 
-35 9 25 
83 -87 -51 
-4 -45 -61 
80 53 37 
-32 -35 -26 
33 15 -89 
9 61 -3 
95 -6 -28 
57 50 24 
-50 65 5 
23 58 73 
99 -92 -45 
-33 35 17 
100 72 -96 
62 65 34 
84 -63 -33 
-57 -59 11 
-73 -91 -11 
-2 13 23 
17 45 -33 
84 85 46 
53 22 81 
54 -21 -81 
67 88 -90 
37 61 -5 
-58 45 -91 
-11 -1 -46 
9 65 10 
-78 96 3 
-39 -68 -80 
83 47 -70 
-35 -9 6 
-94 -96 95 
53 82 25 
-26 100 -30 
-20 99 53 
55 39 58 
74 -37 -100 
55 -79 98 
74 12 72 
17 -55 -52 
-28 -37 44 
-9 -20 -83 
59 11 -53 
68 4 87 
100 -6 -57 
-66 -71 -51 
69 -36 62 
-7 -51 -63 
-15 89 40 
-28 45 93 
52 -18 -6 
-84 -41 -36 
-88 21 14 
-12 -47 -63 
63 41 88 
77 27 -78 
82 -86 -21 
-81 47 36 
-59 -97 -33 
97 -27 -67 
-26 -65 -4 
-54 -11 64 
8 -60 -34 
-18 -28 -96 
-66 -31 69 
63 17 -32 
-7 38 54 
51 43 29 
-58 98 3 
-12 7 82 
-29 -9 -51 
60 -5 -45 
97 -43 -63 
5 96 7 
-30 49 48 
85 61 100 
-92 69 -50 
-8 46 -73 
39 -43 83 
31 85 -52 
-98 -82 7 
72 -37 75 
-53 60 72 
36 -45 -68 
-86 62 -71 
78 31 98 
46 -38 16 
44 -15 -13 
-11 70 24 
-88 65 -73 
-5 -74 -51 
54 88 42 
9 -77 -95 
-27 16 78 
-62 -66 39 
37 -61 -24 
-6 -80 -82 
87 50 22 
-76 84 49 
98 28 83 
-76 81 -17 
77 -8 10 
-40 -53 -9 
97 73 -55 
-33 -83 35 
35 -33 23 
5 -45 -51 
65 -29 55 
94 -40 23 
28 3 -2 
-20 -1 -52 
50 -61 14 
-42 14 56 
40 27 -79 
-13 12 -54 
62 -12 -86 
-8 -63 -100 
42 24 89 
-82 -80 41 
-12 5 93 
-3 -53 84 
87 22 1 
-16 65 72 
-73 93 -62 
49 98 37 
36 -69 62 
96 98 30 
47 10 2 
-14 -94 -10 
51 -44 20 
-55 6 -100 
-13 95 -47 
-59 32 69 
-8 -13 -84 
-70 -55 -33 
-17 50 10 
45 -14 25 
-55 -45 -19 
89 -72 96 
-69 68 96 
-3 -56 -27 
26 -77 53 
94 8 -58 
95 47 33 
70 36 5 
59 97 -31 
-82 28 16 
-97 5 96 
-68 -63 -49 
-72 55 -44 
23 -84 -88 
24 -23 16 
34 5 33 
47 -34 4 
-10 -64 -14 
-86 -88 30 
-16 -83 -21 
-73 -94 -78 
45 -32 -4 
94 80 31 
47 -36 -22 
13 -91 -70 
-90 38 -28 
-31 69 -68 
23 -20 34 
95 6 4 
-16 61 -46 
5 91 28 
87 -67 -8 
-89 40 50 
-47 -34 33 
-95 74 46 
-53 -33 69 
-10 45 99 
66 -74 -1 
25 -97 -21 
14 19 66 
-51 -85 -5 
8 31 100 
96 75 79 
56 84 50 
24 4 -48 
90 -67 -47 
32 -35 73 
4 65 -58 
-30 -68 -49 
51 86 -13 
18 -74 -32 
95 89 -77 
-3 60 -96 
77 16 -24 
-36 52 27 
92 -3 81 
-82 -39 7 
-16 -68 -31 
83 37 -1 
91 -60 -2 
-53 -8 40 
-9 -36 -88 
99 62 -56 
-24 -35 65 
-7 -71 62 
-52 79 14 
51 44 16 
28 93 39 
59 -94 68 
-18 -32 -54 
-80 70 -22 
45 61 38 
25 -60 -76 
24 -65 -13 
73 92 85 
76 -99 11 
89 25 55 
-74 -91 47 
47 70 -13 
-95 -17 96 
58 -97 -35 
71 41 11 
-77 -16 90 
8 78 -44 
21 52 100 
-12 -52 -85 
-48 -94 19 
-46 -72 -4 
82 -19 -76 
-63 -69 43 
71 14 52 
-50 48 -60 
-16 60 29 
-21 78 -89 
66 -20 74 
53 -87 77 
-21 -67 8 
52 57 -95 
45 -35 16 
48 -94 51 
91 23 41 
26 47 15 
-67 42 30 
69 11 88 
77 65 28 
55 77 -66 
64 -11 88 
73 -26 -27 
96 65 5 
-27 7 -77 
-21 56 -6 
-87 48 96 
-37 -87 -70 
63 -57 33 
83 7 4 
17 -14 -38 
22 -18 3 
7 27 -72 
53 -81 -51 
23 -75 -91 
60 -68 40 
-49 -25 -71 
53 -77 78 
3 64 -65 
3 -14 32 
10 -80 -43 
73 40 100 
-78 -94 79 
68 73 14 
17 36 -40 
-43 -45 -1 
36 -30 97 
-53 86 -20 
6 68 -21 
48 29 80 
-94 65 -81 
-100 -33 -28 
-31 33 -68 
52 -77 -31 
43 75 -62 
-72 31 60 
92 56 -48 
53 51 60 
25 -18 -49 
-80 43 -9 
-95 64 54 
93 96 67 
9 -58 82 
-56 79 33 
-10 33 59 
-33 46 94 
-55 -53 -83 
-75 85 -26 
-33 -53 -91 
45 69 25 
91 -9 -83 
-16 38 20 
-76 -86 -85 
-50 42 29 
84 19 -67 
40 98 79 
18 95 93 
88 -25 40 
51 -35 -50 
-66 40 -62 
-81 24 67 
16 85 -27 
53 57 49 
71 30 11 
30 20 -17 
-30 -40 -59 
-41 -91 2 
81 12 -2 
73 -52 -44 
75 73 8 
75 -49 47 
69 -33 26 
-68 50 -57 
-11 -55 -85 
75 -55 -85 
11 49 6 
-59 37 -68 
78 -48 43 
88 -86 54 
92 -3 -31 
-63 85 52 
41 93 79 
36 -47 -91 
67 73 51 
51 -91 -13 
-24 68 -75 
41 40 -7 
27 78 12 
-79 -89 58 
-86 -1 93 
-52 -56 -47 
-87 -19 93 
-63 18 -32 
63 55 -35 
-80 75 67 
-100 -68 -41 
81 7 74 
-79 83 48 
-25 19 92 
-38 -31 -91 
6 55 21 
-16 -51 49 
-96 7 60 
100 63 87 
23 15 52 
49 -88 25 
-95 -15 23 
-13 79 -10 
74 -63 89 
42 -18 58 
52 26 -25 
-38 98 65 
65 -42 -35 
14 30 100 
66 45 -68 
29 -98 -63 
19 -15 -11 
-76 44 10 
-48 49 85 
-64 -66 91 
16 -18 24 
-93 -87 19 
29 -2 -38 
73 51 64 
56 -15 -21 
-41 43 -86 
61 4 16 
91 46 -76 
3 -54 -31 
35 39 -65 
44 -33 22 
-33 -53 70 
87 -50 81 
46 25 62 
-92 43 -41 
1 -2 4 
-34 -48 -61 
-52 7 -22 
63 -89 11 
23 64 81 
70 16 -95 
7 -82 -94 
-93 -7 13