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