魔法师(wizard)

问题描述

小M正在玩一个冒险游戏。游戏中，他是一名魔法师，需要在一片神秘的森林中使用法术击败各种怪物。

击败每个怪物都会给予小M一种法术，但是小M只能同时保持一种法术，如果击败新的怪物会遗忘之前的法术。当然，使用不同的法术击败不同的怪物需要不同的回合数。每次使用法术都需要消耗一定的法力值，小M的总法力值是有限的。

他拥有一个道具，这使得他击败第一个怪物不需要时间和法力值。

现在小M希望以最快的速度击败所有怪物，但是他不知道怎么样操作最快。请你帮帮他。

输入格式

输入共 $2n + 1$ 行。第一行两个整数 $n$ 和 $m$，分别表示怪物的数量和小M的法力值。

接下来 $n$ 行，其中每行 $n$ 个整数，第 $i$ 行第 $j$ 个整数记为 $w_{i,j}$，表示使用怪物 $i$ 提供的法术击败怪物 $j$ 需要的回合数。本题中出现的怪物编号都是从 $1$ 到 $n$ 的正整数。

接下来 $n$ 行，其中每行 $n$ 个整数，第 $i$ 行第 $j$ 个整数记为 $c_{i,j}$，表示使用怪物 $i$ 提供的法术击败怪物 $j$ 需要的法力值。

输出格式

如果无解，输出一行一个整数 $-1$。

在有解的情况下，输出共 $2$ 行。第 $1$ 行一个整数，表示在小M的法力值允许的情况下击败所有怪物的最短回合数。第 $2$ 行为 $n$ 个整数的编号序列，第 $i$ 个整数表示小M击败的第 $i$ 个怪物编号（含起点与终点）。如果存在多个最优解，请输出使得该编号序列字典序最小的一条。

注意，“字典序比较”是指“逐点比较”而非“逐字符比较”，如 $2,10$ 的字典序小于 $10,2$。

样例输入

4 18
0 9 8 5
7 0 2 3
6 4 0 8
1 7 1 0
0 8 8 8
4 0 8 6
8 5 0 8
9 3 5 0

样例输出

10
1 4 3 2

样例说明

操作顺序为 1 → 4 → 3 → 2 ，总回合数为 5 + 1 + 4 = 10，法力总花费为 8 + 5 + 5 = 18，是法力不超过上限的最快过程。

值得注意的是，虽然存在更快速的操作顺序 3 → 2 → 4 → 1，总回合数为 4 + 3 + 1 = 8，但是其法力花费为 5 + 6 + 9 = 20，超过了法力上限。

数据范围与约定

对于 $10\%$ 的数据，$n\le 5$。

对于 $30\%$ 的数据，$n\le 10$。

对于 $50\%$ 的数据，$n\le 13$。

对于 $70\%$ 的数据，$n\le 16$。

对于$100\%$ 的数据，$3\le n\le 18,0\le m\le10^9$​。对任意 $i \le j$，有 $0 \le w_{i,j} \le 10^6，0 \le c_{i,j} \le 10^6$，$w_{i,i}$ 和 $c_{i,i}$ 的值在本题中无意义，输入数据中取值为 $0$。所有的 $w_{i,j},c_{i,j}$ 在数据范围内随机生成，$m$ 以一条随机操作序列的总花费为基础，在其附近随机取值。