该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

该题为孵化器实验室一轮考核第四期的C题，考查大家对路径规划和深度搜索的理解。

最后一次，需要一点不一样的东西～

比如，一颗红色恒星

程序要求

简单来说！

你乘坐的列车在太阳内部的行驶出现了问题，似乎遇到了一点危险？

由于除了起点和终点外，其余所有站点都在太阳内部

所以你要帮助列车在一个有 $N$ 个站点的路线图里找到一条从起点到终点能量消耗最少的路线，这样就能尽最大可能离开太阳

但麻烦的是，这条路线必须经过所有 $K$ 个必经站点

都怪列车的死板控制程序，出问题了还想着经过必经站点，真是的

输入

第 $1$ 行一个正整数 $N$ 表示站点个数，一个正整数 $M$ 表示列车初始拥有的能量。

(起点为站点1，终点为站点n，所有站点都可以被重复经过)

接下来 $N$ 行一个 $N × N$ 的矩阵，第 $i$ 行第 $j$ 列的整数 $E(i,j)$ 表示从站点 $i$ 到站点 $j$ 所需的能量消耗。

_{注意：由于太阳内部的环境复杂多变，$E(i,j)$ 不一定等于 $E(j,i)$}

第 $N+2$ 行一个整数 $K$ ，表示必须经过的站点个数

第 $N+3$ 行共 $K$ 个正整数，表示必须经过的站点编号 （终点一定在这里写出）

输出

第 $1$ 行一个整数 $E$ ，表示完成路线所需的最小能量消耗

第 $2$ 行为字符串 “YES” 或字符串 “NO”

_{PS："YES"表示列车能够完成路线$(E \leq M)$，"NO"表示列车无法完成路线 $(E > M)$}

Sample1

2 3
0 4
5 0
2
1 2

答案路线：1 -> 2

4
NO

Sample2

3 5
0 8 2
1 0 1
9 0 0
2
2 3

答案路线：1 -> 3 -> 2 -> 3

3
YES

背景

深邃的太空中，黑红色的观光列车静静地漂浮在小行星带之间…

透过豪华车厢的全景天窗，你能看到已转变为红巨星的太阳就在不远处。

………

你走出房间，发现其他乘客都不在了。

“嗯…有人在吗？”

呃，似乎你被困在这里了。

话说回来，为什么这辆列车只是漂浮在这里呢？它没有什么地方要去吗？

仔细一想，这样的情况似乎持续很久了，列车的能源已经耗尽，燃油也在不断泄漏，6号车厢的墙壁甚至一半不见了踪影……

………

不能再这样下去了！对啦，走一走，瞧一瞧，好事总是会有的嘛！

好在你在附近的小行星上找到了一块奇怪的黄色能量晶体，你把它丢进了锅炉房，列车恢复了一点动力

车轮开始转动，周遭的碎片斑驳陆离，沉重的轰鸣声在墙体中传播……通往未知世界的旅途正等待着你

...

“尊敬的各位旅客，欢迎搭乘烈冕号观光列车，本次旅程我们来到了故乡太阳系并参观晚期恒星，列车将从太阳南极出发，途经太阳内部，最终到达太阳北极，很高兴即将与您共同展开一段奇妙的旅程，祝您旅途愉快。”

“下一站，光球层”

………

列车开始行驶，窗外的小行星向后快速退去，紧接着，列车冲破了太阳大气。

“下一站，对流层”

………

这可不行！你注意到列车的能源消耗迅速加大，也许有点夸大其词，但这样下去会出不去的！

“下一站，辐射区”

………

你试图让列车原路返回，但却没有做到，似乎列车的观光路线程序要求其必须经过中途的特定几个站点？

“下一站，日核”

………

总之！你发现自己仍然能调整列车经过站点的顺序，现在规划一条从南极到北极的最短路线，在能源耗尽前离开太阳吧！

日志

…

281053年前 | INFO | 列车#L-hyWDc4 “程序运行。已设置 'M34HMA_S' 作为始发站，'M34HMA_N' 作为终点站”

281053年前 | INFO | 列车#L-hyWDc4 “ 已设置 [ 'R03' , 'D01' , 'H00' , ... ] 作为必经站点 ”

281053年前 | INFO | 列车#L-hyWDc4 “ 已设置 [ 'R07' , 'F12' , 'H02' , ... ] 作为中转站点 ”

281053年前 | INFO | 列车#L-hyWDc4 “ 耗能计算完毕 ，已写入到 'energyConsume.MATRIX' "

281052年前 | INFO | 列车#L-hyWDc4 “ 已发车。正在前往 'M34HMA_S' ”

281048年前 | INFO | 列车#L-hyWDc4 “ 已抵达 'M34HMA_S' 。等待人员苏醒”

281048年前 | WARNING | 列车#L-hyWDc4 “ 检测到原因未知的能源故障。正在尝试修复并联络外界 ”

281048年前 | ERROR | 列车#L-hyWDc4 “ 修复失败。联络失败。未检测到以下组件 [ CR_E[11,12] , CR_F[1,2,3,...] , CR_G[1,3] , ... ] "

281048年前 | INFO | 列车#L-hyWDc4 “ 正在扫描周遭环境。尝试寻找替代能源 ”

281048年前 | INFO | 列车#L-hyWDc4 “ 未发现可用的替代能源 "

281046年前 | WARNING | 列车#L-hyWDc4 “ 10分钟内未收到用户命令。所有系统进入休眠 ”

17分22秒前 | INFO | 列车#L-hyWDc4 “ 检测到少量的能源恢复。即将根据之前的设置，完成原定路线 "

02分04秒前 | ERROR | 列车#L-hyWDc4 “ 路线更改失败。路线必须包括所有的必经站点 ”

00分39秒前 | INFO | 列车#L-hyWDc4 “ 路线更改成功 "

LimiTation

今天我们有一般宽松的一些数据

_{不过如果你觉得数据范围太简单，也可以想一下 $N$ 或 $K$ 增大后的解法}

$2 \leq N \leq 100$

$0 \leq K \leq 11$

$0 \leq M \leq 10^{10}$

$0 \leq E(i,j) \leq 10^{10}$

注意！情况紧急，你只有500ms的时间！