D. Girona Flower Time
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For more than 60 years, the city of Girona has celebrated the flower exhibition "Girona temps de flors," where every corner and iconic space of the old town is decorated with flowers. The result is a city full of flowers and, of course, curious tourists from all over the world filling the streets of the old town of Girona to enjoy the wonderful exhibition.

But like everything, there is a dark side. The poor citizens who live peacefully throughout the year in the old town see their streets infested with tourists who seem unable to distinguish between a road and a sidewalk, or between a flower and a car that wants to pass.

After years of living in the old town of Girona, this year Cesc is going to fulfill the secret dream of all the residents of his neighborhood: to push as many tourists as possible on his way home!

This year, the exhibition consists of $$$n$$$ points decorated with flowers, at point $$$i$$$ there are $$$t_{i}$$$ tourists taking photos. The old town has a large number of alleys, and between each two flower exhibition points, there is an alley that connects them. The alley that goes from point $$$i$$$ to point $$$j$$$ has a length of $$$a_{ij}$$$; keep in mind that the alleys are one-way.

Cesc starts at point $$$0$$$ and wants to go home, which is at point $$$1$$$, pushing the maximum number of tourists possible. However, he is a bit in a hurry and does not want to take more than $$$S$$$ seconds, as he travels one unit of distance per second and can push the tourists without losing time. How many tourists can he push on his way home at most?

**Important**: To go from point $$$i$$$ to point $$$j$$$, it is not necessary to use the direct alley; any combination of alleys can be used.

Each tourist can only be pushed once.

It is guaranteed that he always has time to go from point $$$0$$$ to point $$$1$$$.

Input

The input consists of several cases.

Each case starts with the integers $$$n$$$, $$$S$$$.

The following line contains the $$$n$$$ integers $$$t_{i}$$$.

Each of the next $$$n$$$ lines contains the integers $$$a_{ij}$$$. Line $$$i$$$ contains the integers $$$a_{i0}, a_{i1}, ..., a_{in}$$$.

Output

One line for each case with the answer.

Scoring

$$$1 \leq a_{ij}, t_{i} \leq 1000$$$

$$$a_{ii} = 0$$$

$$$1 \leq S \leq 20000$$$

11 points $$$\; \; 2 \leq n \leq 8 \; \;$$$ and $$$\; a_{ij} = 1 \; \;$$$ for all distinct $$$i$$$ and $$$j$$$.

12 points $$$\; \; 2 \leq n \leq 8 \; \;$$$ and $$$\; a_{ij} \; \;$$$ is the minimum time to go from $$$i$$$ to $$$j$$$.

13 points $$$\; \; 2 \leq n \leq 8 \; \;$$$

11 points $$$\; \; 2 \leq n \leq 15 \; \;$$$ and $$$\; a_{ij} = 1 \; \;$$$ for all distinct $$$i$$$ and $$$j$$$.

12 points $$$\; \; 2 \leq n \leq 15 \; \;$$$ and $$$\; a_{ij} \; \;$$$ is the minimum time to go from $$$i$$$ to $$$j$$$.

13 points $$$\; \; 2 \leq n \leq 15 \; \;$$$

28 points $$$\; \; 2 \leq n \leq 18 \; \;$$$

Examples
Input
4 4
887 778 916 794
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
Output
3375
Input
3 1379
650 422 363
0 887 778
916 0 794
336 387 0
3 454
173 737 212
0 28 691
60 0 751
601 541 0
Output
1435
910
Input
8 7246
171 997 282 306 926 85 328 337
0 384 887 778 916 794 336 387
493 0 650 422 363 28 691 60
764 927 0 541 427 173 737 212
369 568 430 0 783 531 863 124
68 136 930 803 0 23 59 70
168 394 457 12 43 0 230 374
422 920 785 538 199 325 0 316
371 414 527 92 981 957 874 0
Output
3432