그냥 부트폴

축구가 항상 아메리카 대륙에서 가장 인기 있는 스포츠였던 것은 아니다. 역사학자들은 대륙 곳곳의 여러 문명에서 행해진 고대 스포츠에 관한 기록을 찾아냈다. 구전 전통이 없어 원래 이름은 알려지지 않았지만, 현대에 들어와서는 아주 창의적으로 "부트폴"이라는 이름이 붙었다.

부트폴에 관해서는 기본 규칙조차 알려진 것이 많지 않다. 그러나 고고학자들은 부트폴 코치들이 팀을 구성하려고 할 때 남긴 많은 메모를 발견했고, 이를 통해 팀이 어떻게 만들어졌는지에 관한 정보를 얻을 수 있다. 이 메모들은 숫자와 계산으로 가득하다. 부트폴 코치들은 선수들을 가능한 최적의 위치에 배치해 팀을 최적화하려고 꼼꼼히 노력했다. 이 작업을 돕기 위해 코치들은 각 배치의 성능을 판정하는 지표를 개발했다.

부트폴 경기장에는 M개의 위치가 있고, 이들은 일렬로 늘어서 있다. 부트폴 팀은 N명의 선수로 이루어지며, 각 선수는 어떤 위치에 배정된다. 모든 선수는 정확히 하나의 위치에 배정되어야 하고, 각 위치에는 한 명 이상의 선수가 있을 수도 있고 아무도 없을 수도 있다.

당연히 선수들은 서로 같지 않다. 선수마다 경기장의 위치에 따라 다른 성능을 낼 수 있다. 구체적으로, 각 선수 i와 각 위치 j에 대해 양의 값 Pi,j가 있고, 이는 선수 i가 위치 j에서 뛸 때의 성능을 나타낸다.

문제를 더 복잡하게 만드는 것은 코치들이 선수 간 상호작용도 고려한다는 점이다. 어떤 선수 쌍은 "절친"이다. 절친이 경기장에서 서로 멀리 떨어져 있으면 팀 성능이 떨어진다. 양의 값 C는 절친을 서로 멀어지게 할 때 치르는 성능 패널티를 나타낸다.

선수들이 위치에 배정되고 나면 팀 성능 값은 다음과 같이 계산된다. 먼저, 선수들이 배정된 위치에서 뛸 때의 성능을 모두 더한다. 그다음, 절친인 선수 쌍마다 C 곱하기 두 선수 사이의 거리를 뺀다. 여기서 두 선수 사이의 거리는 두 선수가 배정된 위치 차이의 절댓값으로 정의된다.

우리는 부트폴 코치들이 팀을 얼마나 잘 구성했는지 알고 싶다. 그러기 위해 각 위치에서의 선수 성능과 절친인 선수 쌍이 주어졌을 때, 선수들을 최적으로 배치해 얻을 수 있는 팀 성능의 최댓값을 구하려고 한다.

첫째 줄에 네 정수 N, M, K, C가 주어진다(1 ≤ N, M ≤ 50, 0 ≤ K ≤ 50, 0 ≤ C ≤ 106). 이는 각각 선수의 수, 위치의 수, 절친인 선수 쌍의 수, 절친을 서로 멀리 떨어뜨릴 때의 패널티를 나타낸다.

다음 N개 줄 각각에 M개의 정수가 주어진다. i번째 줄의 j번째 정수는 Pi,j이며, 선수 i가 위치 j에서 뛸 때의 성능을 나타낸다(0 ≤ Pi,j ≤ 106).

다음 K개 줄 각각에 두 정수 ai와 bi가 주어진다(1 ≤ ai < bi ≤ N). 이는 선수 ai와 bi가 절친임을 나타낸다. 이 목록에 같은 선수 쌍이 두 번 나오지 않는다.

가능한 팀 성능의 최댓값을 나타내는 정수 하나를 한 줄에 출력한다.

(이 경우 최적해는 선수 1과 3을 위치 2에, 선수 2를 위치 3에 배정하는 것이다. 그러면 선수 성능의 합은 2+8+9=19이고, 선수 1과 2가 거리 1만큼 떨어져 있으므로 패널티 5를 치르며, 선수 1과 3은 같은 위치에 있으므로 패널티 0을 치른다.)