FRAKTAL - konkurs programistyczny

Jaś zabrał się za uprawę bananów. Nie wziął jednak pod uwagę, że klimat potrafi być bardzo surowy, więc teraz musi przygotować odpowiednie zadaszenie.

Jaś ma długą farmę o wymiarach 2xN. Na niektórych polach rosną palmy. Celem jest pokrycie wszystkich D palm prostokątnymi dachami. Dachy mogą być dowolnymi prostokątami o całkowitych wymiarach. Nie mogą wychodzić poza obszar farmy ale mogą pokrywać puste pole. Dachy nie mogą się pokrywać.

Twoje zadanie to policzyć jaka jest najmniejsza możliwa powierzchnia K dachów, które pokryją wszystkie palmy.

Wejście

W pierwszej linii wejścia znajduje się t - liczba zestawów danych (t ≤ 10).

Każdy test wygląda następująco:

Na początku podane są trzy liczby: D - liczba palm (D ≤ 2500), K - liczba dachów (K ≤ D), N - rozmiar pola (N ≤ 10⁶).

W kolejnych D liniach znajdują się pary liczb a, b oznaczające współrzędne kolejnych palm (a ∈ [1,2], b ∈ [1, N]).

Wyjście

Najmniejsza powierzchnia K dachów, które przykryją wszystkie D palmy.

Przykład

Wejście:

2
8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4
6 2 100
1 1
1 2
1 3
2 2
2 3
2 4

Wyjście:

10
6