一个小男孩杰拉尔德走进一家服装店,发现了一些非常不愉快的事情:并不是所有的衣服都相配。例如,杰拉德注意到他穿着吸烟装、戴着棒球帽看起来相当可笑。
商店总共出售 n 件衣服,并且恰好有 m 件衣服匹配。每件商品都有其价格,以整数卢布表示。杰拉德想买三件衣服,以便它们相互搭配。而且,他还想花尽可能少的钱。找出他能花的最少金额。
输入
第一个输入文件行包含整数 n 和 m — 商店中的服装商品总数以及匹配的服装商品对总数 ($$3 \leq n \leq 100, 0 \leq m \leq \frac{n(n-1)}{2}$$)。
下一行包含 n 个整数 ai (1 ≤ ai ≤ 106) — 服装商品的价格(以卢布为单位)。
接下来的 m 行每行包含一对空格分隔的整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi)。每对这样的数字都意味着第 ui 件衣服和第 vi 件衣服相互匹配。保证每对中 ui 和 vi 不同,并且所有无序对 (ui, vi) 都不同。
输出
打印唯一的数字——杰拉尔德在商店中必须支付的最少卢布金额。如果商店没有三件相互匹配的服装,请打印“-1”(不带引号)。
示例
输入 #1
3 3 1 2 3 1 2 2 3 3 1
输出 #1
6
输入 #2
3 2 2 3 4 2 3 2 1
输出 #2
-1
输入 #3
4 4 1 1 1 1 1 2 2 3 3 4 4 1
输出 #3
-1
注意
第一个测试中只有三件衣服,而且它们都是相互匹配的。那么,只有一个办法——买这3件衣服;在这种情况下,他花费了 6 卢布。
第二次测试也只有三件衣服,但杰拉德买不到,因为第一件衣服与第三件衣服不匹配。因此,不存在三件相配的衣服。答案是-1。
在第三个示例中,有 4 件衣服,但 Gerald 不能同时购买其中的任何 3 件。答案是-1。