시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

3 3 2 1

예제 출력 1

5

예제 입력 2

3 3 1 1

예제 출력 2

-1

예제 입력 3

5 10 5 2

예제 출력 3

50

출처