현상금 헌터

무한히 넓은 $2$차원 평면에서 $N$명의 도둑이 도망쳤다.

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

도둑들은 처음 있던 정수 좌표 지점에서 동서남북 중 정해진 한 방향으로만 1시간 동안 속력 1로 계속 움직인다.

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

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

무지와 도둑이 같은 시각에 같은 위치에 있으면, 무지는 1시간을 써서 그 위치에서 해당 도둑을 체포하고 $C_i$만큼의 현상금을 얻는다. 동시에 두 명 이상의 도둑을 잡을 수는 없다. 위치가 실수 좌표여도 체포할 수 있다.

무지는 처음에 원점 $(0,0)$에 있다. 남은 시간 $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$축에 평행하게 이동한다는 점에 유의하자.