Processing math: 100%

Problem F. Fast Breeding

Author:И. Блинов   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

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: (ri, gi, bi).

When two types of plants with colors (ra, ga, ba) and (rb, gb, bb) are crossbred, the color of the new flower is calculated as follows: (ra+rb2, ga+gb2, ba+bb2). 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 ri, gi, bi, 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

1n100

1r,g,b,ri,gi,bi64

Sample tests

No. Standard input Standard output
1
32 32 32
2
1 1 1
64 64 64 
1
2
64 64 64
2
1 1 1
63 63 63 
-1

0.081s 0.032s 13