25912번 - 현상금 헌터

무한한 크기의 $2$차원 평면으로 이루어진 세상에서 $N$명의 도둑들이 도망쳤다.

현상금 헌터 무지는 남은 시간 $T$ 동안 도둑들을 잡아 도둑들에게 붙은 현상금을 최대한 많이 얻고자 한다.

도둑들은 초기에 위치한 정수 좌표 지점에서 동서남북 중 초기에 정해진 한 방향으로만 계속해서 한 시간 동안 $1$의 속력으로 움직인다.

무지는 도둑과 똑같은 속력으로 움직이지만 언제나 동서남북 중 원하는 방향으로 방향을 바꿀 수 있다. 또한 움직이지 않고 제자리에 머무르는 것도 가능하다.

$X$좌표가 증가하는 방향은 동쪽이고 $Y$좌표가 증가하는 방향은 북쪽이다.

만약 무지와 도둑이 동일한 시각에 동일한 위치에 존재한다면 $1$시간을 소모해서 그 위치에서 해당 도둑을 체포하고 $C_{i}$만큼의 현상금을 얻을 수 있다. 단 동시에 두 명 이상의 도둑을 잡는 것은 불가능하고 무지와 도둑이 존재하는 위치가 실수 좌표여도 상관없이 체포할 수 있다.

무지는 처음에 좌표 $\left(0,0\right)$, 즉 원점에 존재한다. 무지를 위해 남은 시간 $T$ 내에 얻을 수 있는 현상금의 합의 최댓값을 구해 주자.

첫 번째 줄에 도둑의 수 $N$과 남은 시간 $T$가 공백을 사이에 두고 정수로 주어진다. $(1 \le N \le 500;$ $1 \le T \le 1\,000)$

두 번째 줄부터 $N+1$줄까지 도둑들의 초기 위치 $X_{i}$,$Y_{i}$ 와 현상금 금액 $C_{i}$, 방향 $D_{i}$가 공백을 사이에 두고 정수로 주어진다. $(-2\,000 \le X_{i} \le 2\,000;$ $-2\,000 \le Y_{i} \le 2\,000;$ $1 \le C_{i} \le 500\,000;$ $0 \le D_{i} \le 3)$

도둑은 $D_{i}$가 $0$이면 동쪽, $1$이면 남쪽, $2$이면 서쪽, $3$이면 북쪽으로 움직인다.

무지가 남은 시간 $T$동안 도둑들을 잡아 얻을 수 있는 총 현상금 합의 최댓값을 출력하자.

무지가 이동할 때는 언제나 $X$축 혹은 $Y$축에 평행하게 이동함을 유의하라.