시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB59201840.909%

문제

이 문제에서 두 지점 사이의 거리는 택시 거리로 계산된다. 두 점 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 택시 거리는 $(|x_1 - x_2| + |y_1 - y_2|)$이다.

앤디를 싫어하는 싸이컴 부원 $N$명이 앤디를 공격하려고 한다. 각 부원이 앤디를 공격할 때, 다음과 같은 성질을 가진다.

  • 각 부원이 앤디를 공격하려면 앤디가 보여야 한다. 시야 방향은 $+x, -x, +y, -y$ 중 하나이고 시야각은 좌우 45도이다. 앤디와 부원이 같은 위치에 있는 경우, 또 시야각에 걸치는 경우에도 볼 수 있다고 가정한다.
  • 앤디를 공격하는 공격력은 부원과 앤디 사이의 거리와 같다.

앤디를 물리치려면 $N$명의 공격력의 합이 앤디의 체력 $k$ 이상이 되어야 한다.

예를 들어, $k=23$이고 아래와 같이 위치하는 경우를 생각하자. 아래 예시는 예제 1과 같다.

위와 같은 위치에서 앤디를 공격할 수 있는 사람은 1과 2 뿐이므로 앤디가 받는 공격량은 17이다. 여기서 3번을 왼쪽으로 5만큼 움직였을 때, 앤디가 받는 공격이 25가 되므로 앤디를 물리칠 수 있고, 이 경우가 최적이다.

$k$와 앤디를 포함한 싸이컴 부원 $N+1$명의 위치 및 시야 방향이 주어질 때, 앤디를 물리치기 위해 필요한 $N$명의 이동 거리의 합의 최솟값을 출력하라. 단, 여러 명이 같은 위치에 존재해도 문제가 없으며, 공간에는 제약이 없어 얼마든지 원하는 방향으로 이동할 수 있다고 가정한다.

입력

첫 줄에 두 정수 $N$과 $k$가 주어진다.

둘째 줄에 앤디의 좌표 $X_0$와 $Y_0$가 주어진다.

셋째 줄부터 $N+2$번째 줄까지 $N$명의 좌표 정보와 시야 정보가 주어진다. 구체적으로 $i+2$번째 줄에는 $i$번째 부원의 좌표 $X_i$와 $Y_i$, 그리고 보는 방향 $S_i$가 주어진다. $S_i$는 0, 1, 2, 3 중 하나이며, 각각 $+x$, $-x$, $+y$, $-y$ 방향을 의미한다.

출력

앤디를 물리치기 위해 필요한 $N$명의 이동 거리의 합의 최솟값을 출력한다.

제한

  • $1 \le N \le 10^3$
  • $1 \le k \le 10^3$
  • $1 \le X_i \le 10^3~(0 \le i \le N)$
  • $1 \le Y_i \le 10^3~(0 \le i \le N)$
  • $0 \le S_i \le 3~(0 \le i \le N)$
  • 입력으로 들어오는 모든 수는 정수이다.

예제 입력 1

3 23
5 5
5 11 3
12 9 1
6 1 0

예제 출력 1

5

노트

문제 이미지의 방향은 아래와 같다.

출처

High School > 서울과학고등학교 > SciOI 2022 E번