Centrala telefoniczna

Limit pamięci: 32 MB

Bajtocka firma telekomunikacyjna Bajtel wkracza na rynek z nową ofertą bezprzewodowych telefonów domowych.

Aby umożliwić funkcjonowanie usługi, Bajtel zamierza wybudować centralę telefoniczną z wieżą, która będzie zapewniała zasięg sieci bezprzewodowej. Wiadomo już, gdzie ta centrala powstanie, ale nie zostało jeszcze ustalone, jak wysoką wieżę należy zbudować. Im wyższa wieża, tym większy będzie miała zasięg i więcej domów będzie nim obejmować, więc firma będzie mogła mieć więcej abonentów, co w oczywisty sposób zwiększy jej dochody. Z drugiej strony, wraz ze zwiększaniem wysokości wieży wzrasta koszt jej utrzymania.

Na terenie Bajtocji jest wiele mieszkań, z których każde ma kształt wielokąta prostego, czyli łamanej zamkniętej bez samoprzecięć, wierzchołków wielokrotnych i nachodzących na siebie krawędzi. W każdym z nich mieszka jedna rodzina, która jest skłonna podpisać z Bajtelem umowę na pewien ustalony miesięczny abonament, jednak tylko pod warunkiem, że firma obejmie swoim zasięgiem całą powierzchnię jej mieszkania.

Miesięczny koszt utrzymania wieży centrali jest zależny od jej wysokości. Każdy bajtometr konstrukcji zwiększa promień kolistego obszaru posiadającego zasięg sieci o bajtometrów, jednak jego utrzymanie kosztuje tyle bajtalarów, ile metrów konstrukcji znajduje się jeszcze nad nim. Wynika to ze względów technicznych - część wieży, która znajduje się niżej, musi utrzymywać ciężar całej konstrukcji, która znajduje się nad nią, musi więc być szersza, solidniejsza, a przez to droższa w utrzymaniu. Wysokość wieży musi się wyrażać całkowitą liczbą bajtometrów.

Znając położenia i kształty wszystkich domów w Bajtocji, kwoty miesięcznego abonamentu, jakie poszczególne rodziny są gotowe zapłacić oraz liczbę , należy znaleźć maksymalny możliwy do uzyskania zysk firmy Bajtel.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis położeń i kształtów domów, kwoty abonamentu deklarowane przez poszczególne rodziny oraz liczbę ,
• wyznaczy maksymalne miesięczne zarobki firmy Bajtel,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem i oznaczające liczbę domów w Bajtocji oraz wzrost zasięgu wieży (w bajtometrach) na każdy bajtometr jej wysokości.

W każdym z następnych wierszy znajduje się opis jednego mieszkania. Zaczyna się on od dwóch liczb całkowitych oraz (, ) oznaczających odpowiednio liczbę wierzchołków -tego wielokątnego mieszkania oraz miesięczną kwotę abonamentu w bajtalarach, jaką deklaruje się zapłacić rodzina w nim mieszkająca. Dalej w tym samym wierszu następuje dokładny opis wielokąta. Składa się on z listy całkowitoliczbowych współrzędnych , kolejnych wierzchołków wielokąta (). Połączone ze sobą są każde dwa kolejne wierzchołki na liście oraz pierwszy wierzchołek z ostatnim. Wszystkie liczby występujące w opisie pojedynczego mieszkania są pooddzielane pojedynczymi odstępami.

Może się zdarzyć, że pewne dwa mieszkania nachodzą na siebie (jeżeli na przykład znajdują się na różnych piętrach tego samego budynku). Może się również zdarzyć, że niektóre mieszkania znajdują się pod centralą Bajtela. Miejsce pod budowę wieży centrali ma współrzędne .

Wyjście

Twój program powinien wypisać w pierwszym i jedynym wierszu wyjścia jedną liczbę całkowitą będącą maksymalnym miesięcznym zyskiem w bajtalarach, jaki może osiągnąć Bajtel, wybudowawszy odpowiednio wysoką wieżę. Możesz założyć, że dla każdych danych wejściowych istnieje taka całkowitoliczbowa wysokość wieży, przy której Bajtel osiągnie dodatni miesięczny zysk.

Przykład

Dla danych wejściowych:

3 2
3 4 -2 0 -3 0 -3 1
6 5 1 2 2 3 2 2 3 4 1 4 1 3
3 1 -2 -8 0 -7 2 -8

poprawną odpowiedzią jest:

6

Wyjaśnienie do przykładu: Bajtel osiągnie największy zysk, jeżeli wybuduje wieżę o wysokości bajtometrów. Wtedy zasięg wieży wyniesie bajtometrów. Zysk z mieszkań abonenckich będzie równy , natomiast koszt utrzymania wieży wyniesie , co daje łączny zysk firmy - bajtalarów.

Uwaga: Możesz założyć, że w 50% testów jest spełniony warunek .

Autor zadania: Marian M. Kędzierski.