TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Description

「布咸陽市門,懸千金其上,延諸侯游士賓客,有能增損一字者,予千金。」--- 呂不韋

古代文人對於字句斟酌非常講究,特別是在律詩絕句中,要以一字表多意更是困難重重。

王荊公絕句云:「京口瓜洲一水間,鐘山只隔數重山。春風又綠江南岸,明月何時照我還?」吳中士人家藏其草,初云,「又到江南岸」,圈去「到」字,注曰「不好」,改為「過」。復圈去改為「入」。旋改為「滿」。凡如是十許字,始定為「綠」。黃魯直詩:「歸燕略無三月事,高蟬正用一枝鳴。」「用」字初曰「抱」。又改曰「佔」,曰「在」,曰「帶」,曰「要」,至「用」字始定。予聞錢伸仲大夫如此。 --- 洪邁 容齋續筆

可見一首好詩也是需經過多次歷練,不斷刪修,才能永傳後世的。

王維--著名的山水田園詩人,這次蒐集了許多字句準備來寫首詩。
然而有些字句是沒辦法同時出現在一首詩中的,因為那樣是會使整首詩變得極為奇怪,就如一山不容二虎一樣。
現在王維已經將許多字句從1-n編號好了,而且對於每個字句都有一個優美度a[i]。
如果兩個字句不相容,我們會說他們是不相容的(廢話),因此這兩個字句是不能同時出現在一首詩裡面的。
當你選好某些字句之後,這些字句的優美度和就稱為詩的優美度。

另外要注意的是,因為字句間都是息息相關的,所以任兩個字句間一定有神秘的關係(意思就是如果字句i與字句j是有神秘關係的話,則必有"i與j不相容"或者"一定存在u使得i與u有神秘關係且u與j有神秘關係")。

現在給你m個不相容關係與n個字句,請問你是否能幫助王維使他組出來的詩擁有最大優美度?

Input Format

第一行包含兩正整數n,m分別代表"字句個數"與"不相容字句組個數"(1<=n<=50000,m<=n+7,m<=n*(n-1)/2)。
接下來有n個正整數,第i個數代表第i個字句的優美度ai
接下來有m行,每行兩個正整數i,j(1<=i.j<=n)代表字句i與字句j是不相容的。

Output Format

輸出一數代表詩的最大優美度。

Sample Input

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

Sample Output

19

Hints

範測應該要選字句1,3,6,7,8。

Problem Source

原TIOJ1528 / INFOR 22nd幹部考(prob E)。

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10