앤디 공격하기

이 문제에서 두 지점 사이의 거리는 택시 거리로 계산된다. 두 점 $(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)$
• 입력으로 들어오는 모든 수는 정수이다.

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