操纵比赛

操纵比赛

Description

某国要进行一场可怕的游戏,据说失败者会被秘密处决...
402班的dalao jyq也被迫参加了这场比赛,由于乔神是 生命科学学科带头人 ,为了保存人类的科研成果,ljt必须救下他!

一共有\(n\)个参赛者(编号从1开始,乔神编号为1)参加这场比赛,比赛两两对决,没有平局,必有胜者,胜者得一分,负者不得分。现在比赛已经进行了一半,每个选手已经有了一个积分\(g_i\ge 0\)。给定接下来\(m\)场比赛的对战者\((x_i,y_i)\)。现在ljt可以hack进比赛的操作系统,操纵一场比赛的胜负,但这样风险很大。因此ljt想要知道,在 保证乔神积分最高(不并列) 的前提下,最少的操纵次数是多少?

Input

  • 第一行两个正整数\(n, m\)
  • 第二行\(n\)个数\(g_1,g_2,...,g_n\)
  • 接下来\(m\)行,每行两个数,第\(i\)行为\((x_i, y_i)\)

Output

  • 如果无论如何操作都不能保证乔神夺冠,输出-1
  • 否则输出一个数,为最小操纵次数

Sample

Input1

2 2
1 2
1 2
1 2

Output1

2

Input2

8 14
0 4 4 0 3 3 1 1 
4 8
8 6
2 7
3 1
2 1
3 4
3 4
4 1
8 1
7 6
8 4
2 1
4 5
4 2

Output2

12

Hint

  • 对于10%的数据,\(n\le 5, m\le 10\)
  • 对于30%的数据,\(n\le 10, m\le 20\)
  • 对于60%的数据,\(n\le 10, m\le 40\)
  • 对于100%的数据,\(n\le 12, m\le 100\)

Source

yyh和ljt把一道题想复杂了,然后发现这个建模非常巧妙。
然后就出出来祸害社会了。
出题人水平有限,不保证数据绝对正确,如果有异议可以联系@ljt12138

信息

难度
9
分类
(无)
标签
递交数
1
已通过
1
通过率
100%
上传者