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.

제한

힌트