Maximizing Treasure Profit under Risk Constraints

You are given a set of n treasure locations. Each treasure has an intrinsic value, and there is an associated risk between every pair of treasures. The total risk of a chosen set of treasures (with at least 2 treasures) is defined as the sum of risks over all distinct pairs in the set, i.e. for a set S, the risk is given by:

[ R(S) = \sum_{\substack{i,j \in S\ i < j}} risk[i][j] ]

Your task is to select a subset of treasures (at least 2 treasures) such that the total risk does not exceed a given risk threshold r, and the sum of the values of the selected treasures is maximized. If no valid subset exists, the answer is 0.

Note: The input is provided via standard input and the result should be printed to standard output.

inputFormat

The first line of input contains two integers n and r, where n is the number of treasures and r is the risk threshold.

The second line contains n integers representing the values of the treasures.

The following n lines each contain n integers. The j-th integer in the i-th of these lines represents the risk between treasure i and treasure j.

outputFormat

Output a single integer representing the maximum profit (sum of treasure values) achievable by selecting a subset of treasures such that the total risk is at most r. If no valid subset exists, output 0.

4 5
8 15 20 30
0 1 2 3
1 0 4 2
2 4 0 1
3 2 1 0

50