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