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