최대 이분 매칭

무방향 그래프에서 매칭은 간선의 부분 집합이며, 이 부분 집합에 속한 두 간선은 정점을 공유하지 않는다. 최대 매칭은 크기가 가장 큰 매칭이다.

다음 조건을 모두 만족하는 그래프 $G$가 존재하는지 판정하고, 존재하면 그러한 $G$에 존재할 수 있는 간선의 최대 개수를 구하는 프로그램을 작성하시오.

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

첫째 줄에 $n_1$, $n_2$, $ans$, $d$가 공백으로 구분되어 주어진다. ($1 \le n_1, n_2 \le 10^9$, $1 \le ans, d \le \min(n_1, n_2)$)

조건을 만족하는 그래프가 존재하지 않으면 -1을 출력한다. 존재하면 그러한 그래프에 존재할 수 있는 간선의 최대 개수를 출력한다.