13425번 - 최대 이분 매칭

무방향 그래프가 주어졌을 때 매칭을 구할 수 있다.

매칭은 간선의 부분 집합으로, 집합에 포함된 간선이 공통된 정점을 공유하면 안되다.

최대 매칭은 부분 집합의 크기가 가장 큰 매칭이다.

다음과 같은 성질을 만족하는 그래프가 존재하는지 확인하고, 존재한다면 그러한 그래프에 존재할 수 있는 간선의 최대 개수를 구하는 프로그램을 작성하시오.

• 그래프 G는 단순 무방향 그래프이다.
• G는 이분 그래프이고, 각 부분의 크기는 n1과 n2이다.
• G의 최대 매칭의 크기는 ans이다.
• 모든 정점의 차수는 d 이상이다.

첫째 줄에 n1, n2, ans, d가 주어진다. (1 ≤ n1, n2 ≤ 10⁹, 1 ≤ ans, d ≤ min(n1, n2))

입력으로 주어진 그래프가 존재하지 않으면 -1을 출력하고, 존재하면 그러한 그래프에 존재할 수 있는 간선의 최대 개수를 출력한다.