Author: | И. Блинов | Time limit: | 1 sec | |
Input file: | Standard input | Memory limit: | 512 Mb | |
Output file: | Standard output |
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?
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 −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.
1 ≤ n ≤ 100
1 ≤ r, g, b, ri, gi, bi ≤ 64
No. | Standard input | Standard output |
---|---|---|
1 |
|
|
2 |
|
|