정해진 수의 최대 이익 배정

가능한 연결마다 이익이 있을 때 정확히 K개의 일대일 연결로 얻는 최대 이익을 구하세요.

첫 줄 $L,R,M,K$ ($1\le L,R\le200$, $0\le M\le10,000$, $0\le K\le\min(L,R)$), 다음 $M$줄에 연결과 $10^6$ 이하의 음이 아닌 이익이 주어집니다.

불가능하면 -1, 아니면 최대 이익입니다.