Description

A company processes an alloy composed of iron, aluminum, and tin. Their workflow is simple. First, they import several raw materials that are iron-aluminum-tin alloys, where the proportions of iron, aluminum, and tin differ among types. Then, they take certain amounts from each raw material, melt and mix them to obtain a new alloy. The new alloy has iron, aluminum, and tin proportions equal to what the customer requires.

Now, the customers provide $n$ types of alloys they need, along with the proportions of iron, aluminum, and tin for each. The company wants to order the minimum number of raw material types such that using these raw materials they can produce all the requested alloys.

Input Format

The first line contains two integers $m$ and $n$, denoting the number of raw material types and the number of alloy types requested by customers, respectively.

Lines $2$ through $m+1$ each contain three real numbers $a_i, b_i, c_i$, representing the proportions of iron, aluminum, and tin in a raw material type, respectively.

Lines $m+2$ through $m+n+1$ each contain three real numbers $d_i, e_i, f_i$, representing the proportions of iron, aluminum, and tin in a requested alloy type, respectively.

Output Format

Output a single integer, the minimum number of raw material types required. If there is no solution, output -1.

10 10
0.1 0.2 0.7
0.2 0.3 0.5
0.3 0.4 0.3
0.4 0.5 0.1
0.5 0.1 0.4
0.6 0.2 0.2
0.7 0.3 0
0.8 0.1 0.1
0.9 0.1 0
1 0 0
0.1 0.2 0.7
0.2 0.3 0.5
0.3 0.4 0.3
0.4 0.5 0.1
0.5 0.1 0.4
0.6 0.2 0.2
0.7 0.3 0
0.8 0.1 0.1
0.9 0.1 0
1 0 0

5

Hint

Constraints

For all test points, it holds that $1 \le m, n \le 500$, $0 \le a_i, b_i, c_i, d_i, e_i, f_i \le 1$, and $a_i + b_i + c_i = 1$, $d_i + e_i + f_i = 1$. There are at most six digits after the decimal point.

Translated by ChatGPT 5