Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_14_20 - Dachy

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 (KD), N - rozmiar pola (N ≤ 106).

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

Dodane przez:Grzegorz Spryszyński
Data dodania:2021-12-17
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.