Maximum bipartite matching

Given bipartite part sizes n1, n2, matching size ans, and minimum degree d, find the maximum possible number of edges, or -1 if impossible.

Medium6GraphGreedyMathCombinatoricsNo attempts yetTime limit2sMemory limit512 MB

Description

Examples3

Problem

In an undirected graph, a matching is a subset of the edges in which no two edges share a vertex. A maximum matching is a matching of the largest possible size.

Decide whether a graph $G$ with all of the following properties exists. If it does, find the largest number of edges such a $G$ can have.

$G$ is a simple undirected graph.
$G$ is bipartite, and its two parts have sizes $n_1$ and $n_2$ .
The size of a maximum matching of $G$ is $ans$ .
Every vertex of $G$ has degree at least $d$ .

Input

The first line contains $n_1$ , $n_2$ , $ans$ , and $d$ , separated by spaces. ( $1 \le n_1, n_2 \le 10^9$ , $1 \le ans, d \le \min(n_1, n_2)$ )

Output

If no graph satisfies the conditions, print -1. Otherwise print the largest number of edges such a graph can have.