Najazd

Limit pamięci: 32 MB

Stało się - Trójkątowie najechali Bajtocję! Bajtocja leży na wyspie i zajmuje całą jej powierzchnię. Wyspa ta ma kształt wielokąta wypukłego (tzn. takiego wielokąta, którego każdy kąt wewnętrzny jest mniejszy od ). W Bajtocji znajduje się pewna liczba fabryk oprogramowania. Każda fabryka przynosi pewne stałe zyski lub straty.

Trójkątowie postanowili opanować taki fragment Bajtocji, który:

• ma kształt trójkąta, którego wierzchołkami są pewne trzy różne wierzchołki wielokąta-wyspy,
• przyniesie im jak największe zyski, tzn. suma zysków i strat przynoszonych przez fabryki znajdujące się na opanowanym terytorium będzie możliwie jak największa.

Król Bajtocji, Bajtazar, zastanawia się, jak duże straty dla gospodarki kraju może przynieść najazd Trójkątów. Pomóż mu i napisz program, który wyznaczy sumę zysków i strat przynoszonych przez fabryki, które chcą opanować Trójkątowie.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis kształtu Bajtocji i położenie fabryk,
• wyznaczy maksymalną sumę zysków i strat przynoszonych przez fabryki znajdujące się w obrębie trójkąta, którego wierzchołkami są pewne trzy różne wierzchołki wielokąta-wyspy.
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę wierzchołków wielokąta-wyspy. Kolejnych wierszy wejścia zawiera po dwie liczby całkowite i (), oddzielone pojedynczym odstępem i oznaczające współrzędne i kolejnych wierzchołków wyspy, podane w kolejności zgodnej z kierunkiem ruchu wskazówek zegara. Wiersz -gi zawiera jedną liczbę całkowitą (), oznaczającą liczbę fabryk. Kolejne wierszy zawiera po trzy liczby całkowite , i (, ), oddzielone pojedynczymi odstępami i oznaczające odpowiednio: współrzędne i -tej fabryki, oraz zysk (dla ) bądź stratę (dla ), którą ta fabryka przynosi. Każda fabryka leży na wyspie-wielokącie, tzn. wewnątrz niej lub na jej brzegu. Kilka fabryk może leżeć w tym samym miejscu, tj. mieć te same współrzędne.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą maksymalną sumę zysków i strat przynoszonych przez fabryki znajdujące się w obrębie trójkąta, którego wierzchołkami są pewne trzy różne wierzchołki wielokąta-wyspy. Może się zdarzyć, że liczba ta będzie ujemna.

Przykład

Dla danych wejściowych:

5
4 1
1 4
8 9
11 5
8 1
4
7 2 3
6 3 -1
4 5 3
9 6 -4

poprawną odpowiedzią jest:

5

Autor zadania: Jakub Radoszewski.