카드 교환하기 - 구름LEVEL
카드 교환하기
Quiz Info
카드 교환하기
100points
Participant
34
Solved Rate
29.4%
8
3

문제


부터 까지의 번호를 가진 명의 사람이 있다. 각 사람들은 부터  사이의 임의의 수 가 쓰여있는 카드를 한 장씩 가지고 있다.

사람들 간에는 총 쌍의 친구 관계가 있다. 모든 친구 관계는 양방향이라서, 번 사람과 번 사람이 친구라면 번 사람과 번 사람도 친구이다. 서로 친구 관계에 있는 두 사람끼리는 서로 들고 있는 카드를 원하는 만큼 교환할 수 있다.

모든 사람들은 각자가 들고 있는 카드에 적힌 수가 자신의 번호와 최대한 비슷하기를 원한다. 어떤 한 사람의 불만족도를 그 사람이 들고 있는 카드에 적힌 수와 그 사람의 번호와의 차이로 정의하고, 전체 불만족도는 모든 사람의 불만족도의 합으로 정의한다.

카드 교환이 적절하게 이루어졌을 때, 가능한 전체 불만족도의 최솟값을 구하라.

입력


첫째 줄에는 사람의 수 과 친구 관계의 수 이 공백으로 구분되어 주어진다.

둘째 줄에는 개의 가 공백으로 구분되어 주어진다. 는 번 사람이 처음에 들고 있는 카드에 적힌 수를 의미한다.

다음 개의 줄에는 친구 관계의 정보 가 공백으로 구분되어 주어진다. 이는 번 사람과 번 사람이 친구 관계에 있음을 의미한다. 모든 친구 관계는 양방향이고, 같은 친구 관계가 중복으로 주어지지 않는다. 

입력에서 주어지는 모든 수는 양의 정수이다.

출력


가능한 불만족도의 최솟값을 출력한다.

Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
67
344156
13
16
36
35
15
56
12
Output
8
Example 2
Input
54
32154
12
23
13
45
Output
0
⋇ Please keep the input and output formats carefully
Q & A
Q&A forum that anyone can ask and answer.
Share your questions and answers with other students and grow together!

Registered Questions (0)