Artist Mimi

Time limit1sMemory limit1024 MB

Summary

Given up to 30 RGB paints and a target color, find the minimum difference achievable by mixing between 2 and 7 paints in equal proportions with floor division.

Level: Medium5 of 10
Topics: Brute force, Combinatorics, Implementation, Math
Solved: No attempts yet

Problem

Mimi is an artist with an excellent sense of aesthetics. She sometimes mixes several paints to make a paint of a new color. One day, while painting, Mimi could not help but be startled. Her favorite gomduri-colored paint had run out. But Mimi has no money to buy new paint. Paint is best when mixed, after all. Mimi decided to mix her remaining paints to make gomduri-colored paint.

First, let us learn about the RGB notation. RGB notation represents a color by mixing red, green, and blue, and each color is expressed as an integer from 0 to 255 depending on its brightness. For example, pink is expressed as rgb(255, 192, 203). This means 255 of red, 192 of green, and 203 of blue were mixed.

To make a new paint, select the paints to mix from the remaining paints and mix them in equal proportions. The new color made by mixing paints P1, P2, ..., PK is as follows in RGB notation.

$rgb\left(\left\lfloor\frac{1}{K}\sum_{i=1}^K R_{P_i}\right\rfloor,\left\lfloor\frac{1}{K}\sum_{i=1}^K G_{P_i}\right\rfloor,\left\lfloor\frac{1}{K}\sum_{i=1}^K B_{P_i}\right\rfloor\right)$

That is, the new R value is obtained by adding the R values of all paints to be mixed and dividing by the number of paints. The fractional part is discarded. The G and B values are obtained the same way.

The difference between color i and color j is as follows.

$|R_i-R_j|+|G_i-G_j|+|B_i-B_j|$

Among the colors that can be made by mixing paints, the one closest to gomduri color, that is, the one with the smallest difference from gomduri color, is called munduri color. Given N paints and the gomduri color, write a program to find the difference between gomduri color and munduri color. However, Mimi is not skilled enough yet, so she can mix at most 7 colors. Also, a paint cannot be used alone without mixing.

Input

The first line gives the number of paints N.

Among the following N lines, the i-th (1 ≤ i ≤ N) line gives the Ri, Gi, Bi values of the i-th paint.

The next line gives the Rg, Gg, Bg values of gomduri color.

All input is integers separated by spaces.

Output

On the first line, print the difference between gomduri color and munduri color.

Constraints

2 ≤ N ≤ 30
0 ≤ Ri, Gi, Bi ≤ 255
0 ≤ Rg, Gg, Bg ≤ 255

Examples2

Example 1
Input
```
3
255 0 0
0 255 0
0 0 255
64 64 64
```
Expected output
```
63
```

Example 2

Input

2
255 255 255
255 130 151
255 255 255

Expected output