Problem F. Fast Breeding ≡

Statement

Risorius is engaged in flower breeding. In her collection, there are n types of plants, and she has an unlimited number of each type. Each plant is characterized by the color of its flower. The color of the i-th plant is encoded by 3 numbers in the range from 1 to 64: (r_i, g_i, b_i).

When two types of plants with colors (r_a, g_a, b_a) and (r_b, g_b, b_b) are crossbred, the color of the new flower is calculated as follows: (⌊r_a + r_b2⌋, ⌊g_a + g_b2⌋, ⌊b_a + b_b2⌋). Furthermore, one of the plants involved in the crossbreeding must always be from the initial set of n plant types, otherwise, the result will be non-viable.

Risorius has received an order for a plant with the color (r, g, b). What is the minimum number of crossbreeding operations needed to obtain the desired plant color?

Input format

The first line contains three integers (r, g, b), which represent the desired flower color. The second line contains one integer n, representing the number of initial plant types. The next n lines each contain three integers r_i, g_i, b_i, representing the color of the i-th plant in the initial set.

Output format

Output −1 if it is impossible to obtain a plant with the desired color. Otherwise, output the minimum number of crossbreeding operations needed to obtain the desired plant.

Constraints

1 ≤ n ≤ 100

1 ≤ r, g, b, r_i, g_i, b_i ≤ 64

Sample tests

32 32 32
2
1 1 1
64 64 64 

1

64 64 64
2
1 1 1
63 63 63 

-1