시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB444100.000%

문제

Futebol nem sempre foi o esporte mais popular das Américas. Historiadores encontraram registros de um antigo esporte que era jogado em muitas civilizações pelo continente. Por causa da falta da tradição de se falar sobre este esporte, o nome original é desconhecido, mas em tempos modernos ele é criativamente chamado de “butefol”.

Nós não sabemos muito sobre butefol, nem as regras básicas. Porém, arqueólogos encontraram muitas anotações feitas pelos técnicos enquanto eles montavam seus times, o que nos deu dicas sobre como os times eram formados. Estas anotações estão lotadas de números e cálculos. Os técnicos de butefol tentaram minuciosamente otimizar seus times ao atribuir os jogadores 'as melhores posições possíveis. Para facilitar esta tarefa, eles desenvolveram uma métrica para determinar a performance de cada arranjo.

Há M posições em um campo de butefol, que são distribuídas em uma linha. Um time de butefol é composto de N jogadores, cada um o qual é designado uma posição (todos os jogadores devem ser designados a uma posição, e cada posição pode ser ocupada por zero ou mais jogadores).

Naturalmente, os jogadores não são todos iguais: cada jogador pode ter performances diferentes quando joga em posições diferentes. Concretamente, para cada jogador i e cada posição j, há um inteiro positivo Pi,j que representa a performance do jogador i quando jogando na posição j.

Para complicar as coisas ainda mais, os treinadores também consideravam o aspecto de interação dos jogadores. Há alguns pares de jogadores que são “melhores amigos”. Quando melhores amigos estão longes um do outro no campo, isto tem um impacto negativo na performance do time. Há um inteiro positivo C que representa a penalidade de performance quando melhores amigos estão longes um do outro.

Uma vez que os jogadores estejam distribuídos no campo, o valor da performance do time é calculado da seguinte maneira: primeiro, nós somamos a performance de cada jogador em sua determinada posição. Em seguida, para cada par de jogadores que são melhores amigos, nós subtraímos C multiplicado pela distância entre os dois jogadores, onde a distância entre dois jogadores é definida pela diferença (em valor absoluto) das posições onde os dois jogadores estão designados.

Nós gostaríamos de saber o quão bem os treinadores de butefol estavam formando seus times. Para isto, nós gostaríamos de saber qual é a maior performance possível de ser alcançada ao designar os jogadores de maneira ótima, dadas as performances dos jogadores em cada posição e os pares de jogadores que são melhores amigos.

입력

A primeira linha contém quatro inteiros N, M, K e C (1 ≤ N, M ≤ 50, 0 ≤ K ≤ 50, 0 ≤ C ≤ 106), representando a quantidade de jogadores, a quantidade de posições, a quantidade de pares de melhores amigos e a penalidade por colocar amigos longe uns dos outros.

Cada uma das N linhas seguintes contém M inteiros. O j-ésimo inteiro da i-ésima linha é Pi,j, representando a performance do jogador i se ele for designado na posição j (0 ≤ Pi,j ≤ 106).

Cada uma das K linhas seguintes contém 2 inteiros ai e bi (1 ≤ ai < bi ≤ N), que representa que os jogadores ai e bi são melhores amigos. Nenhum par de jogadores estará repetido nesta lista.

출력

Imprima uma linha contendo um inteiro, representando o máximo de performance possível para o time.

예제 입력 1

3 3 2 5
5 2 1
3 2 8
1 9 3
1 2
1 3

예제 출력 1

14

힌트

(Neste caso, a solução ótima é designar os jogadores 1 e 3 na posição 2, e o jogador 2 na posição 3, para que a soma da performance dos jogadores seja 2+8+9=19, a penalidade seja 5 pelos jogadores 1 e 2 estarem distantes por 1 posição, e a penalidade seja 0 pelos jogadores 1 e 3 estarem na mesma posição).