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$축에 평행하게 이동함을 유의하라.