← 返回题目列表

Codeforces · 102/A

A. 衣服

中文机器翻译题面 查看原题

一个小男孩杰拉尔德走进一家服装店,发现了一些非常不愉快的事情:并不是所有的衣服都相配。例如,杰拉德注意到他穿着吸烟装、戴着棒球帽看起来相当可笑。

商店总共出售 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。