어메이징 레이스

프로그래밍 대회 참가자를 위한 보물찾기 경주를 연다. 출발 지점과 도착 지점 외에 참가자가 들를 장소가 $n$개 있고, $n \le 20$이다. 장소 $i$($1 \le i \le n$)에는 과제가 하나씩 있어서 그 과제를 수행하면 $p_i$점을 얻고, 과제를 끝내는 데 $t_i$분이 걸린다. 각 과제는 한 번만 수행할 수 있으므로 같은 장소를 두 번 방문하지 않는다. 경주가 시작된 뒤에는 출발 지점으로 돌아갈 수 없고, 도착 지점에 들어서는 순간 경주가 끝난다.

경주는 $T$분 안에 마쳐야 한다. 즉 출발 지점을 떠난 시각과 도착 지점에 닿은 시각의 차이가 $T$분을 넘으면 안 된다. 일부 과제에는 마감 $d_i$가 있는데, 출발 지점을 떠난 뒤 $d_i$분 안에 그 과제를 끝내야 한다는 뜻이다. 장소 $i$에 도착하면 그 장소의 과제를 반드시 수행해야 하므로, 마감까지 과제를 끝낼 수 없을 만큼 늦게 도착하는 일정이라면 그 장소로 이동하는 것 자체가 허용되지 않는다.

과제로 얻을 수 있는 점수 합의 최댓값을 구하여라.

첫째 줄에 양의 정수 $n$과 $T$가 주어진다($T \le 1440$). 다음 $n$개 줄에는 각각 세 정수 $p_i$($1 \le p_i \le 100$), $t_i$($1 \le t_i \le 1440$), $d_i$($-1 \le d_i \le 1440$)가 주어진다. $d_i = -1$이면 과제 $i$에 마감이 없다. 마지막 $n+2$개 줄에는 각각 음이 아닌 정수 $n+2$개가 주어진다. $i$번째 줄의 $j$번째 수는 장소 $i$에서 장소 $j$로 이동하는 데 걸리는 시간(분)이고 1440 이하이다. 출발 지점의 번호는 $n+1$, 도착 지점의 번호는 $n+2$이다.

같은 장소로 이동하는 시간은 0이다. 오르막과 내리막처럼 방향에 따라 걸리는 시간이 달라질 수 있어서, 두 장소 사이의 이동 시간은 양방향이 같지 않을 수 있다.

첫째 줄에 얻을 수 있는 점수 합의 최댓값을 출력한다. 둘째 줄에는 그 최댓값을 얻으려고 수행하는 과제의 번호를 증가하는 순서로, 공백 하나로 구분해 출력한다. 최댓값을 얻는 과제 집합이 여럿이면 사전순으로 가장 앞선 것을 출력한다. 즉 집합의 첫 번째 번호를 가능한 한 작게 하고, 같으면 두 번째 번호를 가능한 한 작게 하는 식으로 정한다.

얻을 수 있는 점수의 최댓값이 0이면 둘째 줄은 빈 줄로 출력한다.