시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 33 20 18 69.231%

문제

미미는 미적 감각이 뛰어난 미술가이다. 미미는 때때로 여러 물감을 섞어 새로운 색의 물감을 만들고는 한다. 어느 날 그림을 그리던 미미는 놀라 자빠질 수밖에 없었다. 미미가 가장 아끼는 곰두리색 물감이 다 떨어졌기 때문이다. 하지만 미미는 새 물감을 살 돈이 없다. 물감은 역시 섞어 써야 제맛이다. 미미는 남은 물감들을 섞어 곰두리색 물감을 만들기로 결심하였다.

먼저 RGB 표기법에 대하여 알아보자. RGB 표기법은 빨간색(Red), 초록색(Green), 파란색(Blue)을 혼합하여 색을 나타내는 방법으로, 각각의 색은 밝기에 따라 0부터 255까지의 정수로 표현한다. 예를 들어, 분홍색은 rgb(255, 192, 203)과 같이 표현한다. 이는 빨간색을 255만큼, 초록색을 192만큼, 파란색을 203만큼 혼합하였다는 의미이다.

새로운 물감을 만들기 위해서는 남아 있는 물감 중 혼합할 물감들을 선택한 후 이들을 동일한 비율로 섞는다. P1, P2, ..., PK번 물감을 섞어 새로 만들어지는 색은 RGB 표기법으로 다음과 같다.

$$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)$$

즉, 새로운 R 값은 혼합할 모든 물감의 R 값을 더한 후 이를 물감의 개수로 나누어 구한다. 이때 소수점은 버린다. G와 B 값도 동일한 방법으로 구한다.

색 i와 색 j의 차이는 다음과 같다.

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

물감들을 섞어서 만들 수 있는 색 중 곰두리색에 가장 가까운, 즉 곰두리색과의 차이가 가장 작은 색을 문두리색이라고 한다. N개의 물감과 곰두리색이 주어졌을 때, 곰두리색과 문두리색의 차이를 구하는 프로그램을 작성하시오. 단, 미미는 아직 실력이 부족하여 최대 7개의 색만을 혼합할 수 있다. 또한 물감을 섞지 않고 단독으로 사용할 수 없다.

입력

첫 번째 줄에 물감의 개수 N이 주어진다.

이후 N개의 줄 중 i(1 ≤ i ≤ N)번째 줄에는 i번 물감의 Ri, Gi, Bi 값이 주어진다.

다음 줄에 곰두리색의 Rg, Gg, Bg 값이 주어진다.

모든 입력은 정수이며 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 곰두리색과 문두리색의 차이를 출력한다.

제한

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

예제 입력 1

3
255 0 0
0 255 0
0 0 255
64 64 64

예제 출력 1

63

문두리색은 rgb(85, 85, 85)이다.

예제 입력 2

2
255 255 255
255 130 151
255 255 255

예제 출력 2

115

문두리색은 rgb(255, 192, 203)이다.