다다스는 개의 프리즘 광산을 운영하고 있다. 광산을 운영하려면 채굴 모듈이 필요하므로, 다다스는 개의 채굴 모듈을 만들려고 한다.
번 채굴 모듈에는 개의 후보 설계가 있다. 이 중 정확히 하나를 골라 모듈을 만들어야 한다. 번 후보로 만든 모듈의 성능은 이고, 시간당 개의 프리즘을 소모한다. 모든 모듈을 반드시 만들어야 하며, 소모량은 그 모듈을 사용하는 광산의 수와 관계없이 한 번만 계산한다. 어떤 광산도 사용하지 않는 모듈의 소모량도 계산한다.
번 광산은 서로 다른 두 모듈 를 사용한다. 각 모듈에서 선택한 후보의 번호를 라고 할 때, 이 광산은 시간당 개의 프리즘을 채굴한다. 한 모듈을 여러 광산이 동시에 사용할 수 있다. 같은 두 모듈을 사용하는 광산이 여러 개 있을 수 있으며, 각 광산의 채굴량을 모두 합산한다.
시간당 순이익은 모든 광산의 채굴량 합에서 모든 모듈의 소모량 합을 뺀 값이다. 각 모듈의 후보를 적절히 골랐을 때, 시간당 순이익의 최댓값을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
시간당 순이익의 최댓값을 출력한다. 답은 음수일 수 있다.
첫째 줄에는 광산의 수 과 모듈의 수 이 주어진다. 다음 개의 줄에는 각 모듈의 후보 수와 각 후보의 성능, 소모량이 주어진다. 마지막 개의 줄에는 각 광산이 사용하는 두 모듈의 번호가 주어진다. 후보는 성능순으로 주어진다는 보장이 없다.
| 3 | 55 | 추가적인 제약이 없다. |