Informatica Online Judge

  콩밭을 산책하는 콩충 [2142 / 085E]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 1   Total Tried : 1


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16079]

Background

어느 나라의 양대 산맥을 이루는 명망 높은 두 귀족가가 있다.
그 귀족가를 이끄는 수장인 정용과 민형은 세간의 주목을 받는 앙숙관계이다. 이 나라에는 n개의 영지가 있는데 이 n개의 영지를 정용과 민형은 나눠 관리하고 있다.


한편, 이 나라를 다스리는 윤상에게는 콩충이라는 애완동물이 있다. 윤상에게 있어 가장 중요한 하루의 일과는 바로 콩충을 산책시키는 일이다.

임의의 두 영지 사이에는 조성되지 않은 콩밭이 있다. 윤상에게 잘 보이고 싶은 두 영주들은 각각 자신들의 영지를 한 번씩만 방문하되 산책을 하면서 콩충이 따먹을 수 있는 콩의 개수의 합이 가장 많게끔 콩밭을 조성하여 산책로를 구성해놓았다.
따라서, 하루에 콩충은 산책을 두 번 하게 된다.

민형의 영지와 정용의 영지 사이를 이동할 때에는 전세기를 타고 이동해야 하고, 이는 비용이 상당히 많이 든다.
이에 윤상은 특별 명령을 통하여 두 산책로 사이를 잇는 콩밭을 하나 조성하라고 명령을 내렸다. 물론 콩충이 따먹을 수 있는 콩의 개수가 가장 많은 콩밭을 택할 것이다.

하지만 날이 지나면 지날수록 갈등이 깊어지는 정용과 민형의 관계에 짜증을 느낀 윤상은 영지를 모두 회수하여 국유화하려는 생각을 하게 된다.

영지를 모두 회수하면 콩충이 따먹을 수 있는 콩의 개수가 최대가 되는 새로운 산책로를 구성할 수 있다.

영지를 회수하는 일은 상당히 정치적으로 민감한 일이기에 무턱대고 하는 것이 아니라 신중하게 결정해야 한다.

또, 이미 조성된 산책로의 콩밭을 하나 없애는 데에 그 콩밭에서 따먹을 수 있는 콩의 개수의 20%를 넘지 않는 최대 정수만큼의 손실이 있을 것이라고 보고되었다.

따라서 윤상은 회수하기 전 콩충이 따먹을 수 있는 콩의 개수의 합과 회수 된 후 손실을 고려한 개수의 합을 비교하여 회수 후 합이 더 많을 때에만 영지를 회수하기로 결정하였다.

밀린 업무가 많아 개수의 합을 셀 시간이 없는 윤상을 도와 두 가지 경우의 합을 구하여 영지의 회수 여부를 알려주자.

Input

첫 번째 줄에 영지의 수 N(4<=N<=1000)과 민형의 영지의 수 K(1두 번째 줄부터 N줄에 거쳐 N*N의 인접행렬이 주어진다. 이는 i영지와 j영지 사이 콩밭의 콩의 개수를 의미한다. 콩의 개수는 1개 이상 1000000개 이하이고 임의의 두 영지를 잇는 콩의 개수는 모두 다르다.
N+2 번째 줄에는 민형의 영지 번호가 오름차순으로 K개 주어진다.
N+3 번째 줄에는 정용의 영지 번호가 오름차순으로 N-K개 주어진다.

Output

첫 번째 줄에 회수 전 콩의 개수의 합과 회수 후 콩의 개수의 합을 사이에 공백을 두고 출력한다. 두 번째 줄에 회수 후가 많다면 “After”을, 그 외에는 “Before”을 출력한다.

IO Example

입력1
4 2
0 6 7 8
6 0 9 10
7 9 0 11
8 10 11 0
1 3
2 4

출력1
28 28
Before

해설1
민형의 콩밭은 7이고 정용의 콩밭은 10이다. 3-4를 잇는 콩의 개수가 11으로 가장 많고 이를 다 더하면 28이다.
한편 회수 후에는 1-4, 2-4, 3-4를 연결하는 산책로 29로 가장 많고 1-3 콩밭을 없애야 하므로 7 / 5 = 1.4, 즉 1의 손실이 있어서 최종적으로 28이다.


입력2
5 3
0 10 3 6 9
10 0 13 12 7
3 13 0 8 15
6 12 8 0 14
9 7 15 14 0
1 3 4
2 5

출력2
36 49
After

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]