8589번 - Tort 다국어

Bajtek obchodzi dzisiaj swoje urodziny. Zdmuchnął już wszystkie świeczki z tortu urodzinowego oraz podzielił go na $(n+1)^2$ kawałków. Niestety zrobił to w taki sposób, że kawałki tortu są teraz różnych wielkości, niektóre kawałki są większe, a inne mniejsze od pozostałych. Bajtek wybiera swój kawałek jako pierwszy i chciałby wybrać $k$-ty pod względem wielkości, czyli taki, w którym $k-1$ kawałków jest nie mniejszych od niego, a $(n+1)^2 - k$ kawałków jest nie większych.

Wiemy, że tort urodzinowy Bajtka ma kształt prostokąta oraz że podzielił go $n$ prostymi cięciami wzdłuż jednego z boków prostokąta i $n$ prostymi cięciami wzdłuż drugiego z boków. Chcielibyśmy znać powierzchnię wybranego przez Bajtka kawałka tortu.

W pierwszym wierszu standardowego wejścia znajdują się cztery liczby całkowite $a$, $b$, $n$ oraz $k$ pooddzielane pojedynczymi odstępami ($1 ≤ a, b ≤ 10^9$, $0 ≤ n ≤ 2 \cdot 10^5$, $1 ≤ k ≤ (n+1)^2$), oznaczające odpowiednio długości dwóch boków tortu, liczbę cięć wykonanych przez Bajtka w każdym z kierunków oraz numer szukanego kawałka.

Drugi wiersz zawiera ciąg $n$ liczb całkowitych $x_1, x_2, \dots , x_n$, ($0 < x_i < a)$, gdzie $x_i$ oznacza miejsce $i$-tego cięcia wzdłuż jednego z boków prostokąta (jest to odległość od lewego boku prostokąta). Ponadto zachodzi ($x_j < x_{j+1}$) dla $j = 1, \dots , n-1$.

Trzeci wiersz zawiera ciąg $n$ liczb całkowitych $y_1, y_2, \dots , y_n$, ($0 < y_i < b)$, gdzie $y_i$ oznacza miejsce $i$-tego cięcia wzdłuż drugiego z boków prostokąta (jest to odległość od dolnego boku prostokąta). Ponadto zachodzi ($y_j < y_{j+1}$) dla $j = 1, \dots , n-1$.

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą powierzchni $k$-tego pod względem wielkości kawałka tortu.