Problem B
Amazing Race

A scavenger hunt is being organized for programming contest participants. In addition to the starting and ending locations of the race, there are $n$ ($n \leq 20$) other locations for competitors to travel to. At each location $i$ ($1 \leq i \leq n$), there is a task that must be performed to earn $p_ i$ points. The task at each location takes $t_ i$ minutes to complete. However, each task can only be performed once, so a competitor may not travel to the same location more than once. The competitor cannot return to the starting location after the race begins, and the race finishes as soon as the ending location is reached.

The scavenger hunt must be completed within $T$ minutes. That is, the time between leaving the starting location and arriving at the ending location must be no more than $T$ minutes. In addition, some tasks have a specific deadline $d_ i$, meaning that the task must be completed within $d_ i$ minutes since leaving the starting location. Again, note that if a competitor arrives at location $i$, the task at location $i$ must be performed. If the competitor were to arrive at the location too late and would not finish the task at that location by the deadline, then the competitor would not be allowed to travel to the location at all.

What is the maximum total number of points that can be obtained from the tasks?


The input consists of one case. The first line of input contains two positive integers $n$ and $T$ ($T \leq 1440$). Each of the next $n$ lines contains three integers $p_ i$ ($1 \leq p_ i \leq 100$), $t_ i$ ($1 \leq t_ i \leq 1440$), and $d_ i$ ($-1 \leq d_ i \leq 1440$). If $d_ i = -1$ then there is no deadline for task $i$. Finally, the last $n+2$ lines each contains $n+2$ nonnegative integers. The entry in the $i$th row and $j$th column is the number of minutes ($\leq 1440$) it takes to travel from location $i$ to location $j$. The indices of the starting and ending locations are $n+1$ and $n+2$, respectively.

It is guaranteed that the time to travel from a location to itself is $0$, but the time to travel between two locations in different directions may not be the same (e.g. uphill instead of downhill).


Print the maximum total number of points that can be obtained on the first line. In the second line, print a set of indices of the tasks that need to be performed to achieve this maximum. The list of tasks should be sorted by the indices of the tasks (not by the order in which they are performed). The indices should be separated by a single space. If there are multiple sets of tasks that can achieve the maximum, print the one that is lexicographically smallest. That is, if two sets of tasks achieve the same maximum, the index of the first task in the set should be as small as possible. If there is a tie, the index of the second task in the set should be as small as possible, and so on.

If the maximum number of points that can be obtained is $0$, output a blank line for the indices of the tasks to be performed.

If there is no way of travelling from the starting location to the ending location within $T$ minutes, print $0$.

Sample Input 1 Sample Output 1
3 352
93 82 444
92 76 436
99 62 -1
0 70 66 71 97
76 0 87 66 74
62 90 0 60 94
60 68 68 0 69
83 78 83 73 0
Sample Input 2 Sample Output 2
5 696
96 88 532
99 70 519
96 66 637
90 92 592
95 94 -1
0 67 80 81 60 83 61
72 0 99 68 85 93 82
100 91 0 88 99 70 68
69 65 77 0 65 68 75
63 65 91 96 0 92 100
65 76 85 62 89 0 75
93 83 74 65 88 84 0
1 2 3 5

Please log in to submit a solution to this problem

Log in