测试数据来自 system/1590

背景

笨笨：汗……
路人甲：大汗……
笨笨：瀑布汗……
路人甲：大瀑布汗……
笨笨：懒得和你汗……
路人甲：怎么这么多水的啊？

描述

一场洪水即将到来，笨笨要想方设法堵截它！
堵截洪水的唯一办法是在洪水经过河流的岔道口放上石头！（笨笨在将小石头一颗一颗地垒好……囧）
对于不同的岔道口，需要的石头量不同，而笨笨所要消耗的体力也不同。

为了不太累，笨笨决定要用最少的体力来堵截这场洪水，洪水从岔道0出发，笨笨要防止洪水冲到岔道n。

格式

输入格式

输入有多组，输入第一行为组数（组数小于15）。

每组输入格式如下。

第一行两个数n,m（0<n<=50,0<=m<=200）。

第二行n-1个数，第i个数表示堵截该岔道需要消耗笨笨k[i]的体力。(i=1 to n-1，每个k[i]都是正整数)
接下来m行，每行两个数a,b，表示岔道a和岔道b之间有河道连接。

输出格式

对于每一组输入一个输出。

每组输入输出一行，表示笨笨所需要消耗的最小体力。

若洪水不可能冲到岔道n，则输出“Min!”，若洪水无法阻止，则输出“Max!”。

样例1

样例输入1

1
4 5
2 3 4
0 1
0 3
1 2
2 4
3 4

样例输出1

6

限制

1s

提示

对样例的解释：
洪水从0出发。

而笨笨要阻止洪水流到n。

耗体力最少的堵截方式就是将岔道1和岔道3堵上即可。

消耗体力最小总和为2+4=6。

来源

笨笨原创。