Contest problemset description

Ryszard miał 35 dni na budowę lotniska. Zaniedbał jednak to zadanie, a na domiar złego dopiero teraz wrócił do domu. Na wykonanie tego zadania zostało mu niewiele czasu, więc będziesz musiał mu pomóc.

Teren inwestycyjny to nieskończona siatka kwadratowych pól jednostkowych. W chwili t = 0 Ryszard znajduje się na jednym z pól i rozpoczyna na nim układanie pasa startowego. Jest to jedyne pole lotniska z położonym pasem w tej chwili. Dalsze prace opisuje ciąg poleceń. Przykładowo polecenie W 10 oznacza, że przez następnych 10 jednostek czasu Ryszard będzie przemieszczał się o jedno pole na zachód w każdej jednostce czasu, układając pas na odwiedzanych polach.

Niestety Ryszard jest z natury bardzo skąpy i używa najtańszych materiałów budowlanych. Z tego powodu zbudowany przez niego pas nie jest zbyt wytrzymały – każdy fragment nawierzchni ułożony w chwili t rozpada się i znika dokładnie po x jednostkach czasu, czyli w chwili t + x.

Podczas budowy Ryszard może odwiedzać to samo pole wielokrotnie. Twierdzi jednak, że nigdy nie marnowałby materiałów na pole, na którym nawierzchnia jest już ułożona, bo to się nie opłaca. Innymi słowy, za każdym razem, gdy wracał na dane pole, poprzednio ułożona tam nawierzchnia musiała już zdążyć się rozpaść (ostatnio był na tym polu co najmniej x jednostek czasu temu).

Wyznacz największą możliwą wartość x, dla której Ryszard nie jest kłamcą.

Wejście

W pierwszym wierszu wejścia znajduje się liczba N, oznaczająco ilość instrukcji według, których Ryszard będzie się poruszał. W każdym z kolejnych N wierszy znajduje się kierunek, w którym Ryszard będzie się poruszał (N - góra, E - prawo, S - dół, W - lewo), oraz liczba A, czyli ile kroków wykona w danym kierunku.

Wyjście

W jedynym wierszu wyjścia powinna się znaleźć maksymalna liczba x, dla której Ryszard spełni swoje założenia o wracaniu na pola. Jeśli Ryszard nigdy nie wróci na żadne pole, na którym już był to wypisz  − 1.

Ograniczenia

1 ≤ N ≤ 100, 1 ≤ A ≤ 10.

Podzadanie

Przykład

6
N 10
E 2
S 3
W 4
S 5
E 8

10

5
N 2
W 10
S 3
E 2
N 1

-1

7
E 9
S 5
W 7
N 3
N 4
W 2
S 1

24

N krasnali wybiera się na imprezę. Elementem stroju każdego krasnala jest szpiczasta czapka. We wspólnej garderobie krasnale zgromadziły N czapek. Każdy z nich założy na imprezę dokładnie jedną czapkę. Czapki są różnych długości od 1 do N i każda czapka trafi do dokładnie jednego krasnala.

i-ty krasnal ma wzrost A_i. Jeżeli i-ty krasnal założy czapkę o długości j, to jego sumaryczny wzrost będzie wynosił A_i + j. Krasnale mogą być różnego wzrostu, ale idąc na imprezę chciałyby wyglądać podobnie. W tym celu chcą rozdzielić czapki tak, aby jak najwięcej krasnali miało ten sam sumaryczny wzrost (wzrost krasnala powiększony o długość założonej czapki).

Twoim zadaniem jest napisanie programu, który obliczy i wypisze ile maksymalnie krasnali może mieć taki sam wzrost, po rozdzieleniu i założeniu czapek.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N – liczba krasnali. W drugim i ostatnim wierszu wejścia znajduje się N liczb całkowitych A₁, A₂, …, A_N – wzrosty krasnali.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba całkowita – liczba krasnali, które mogą mieć równy wzrost, przy optymalnym rozłożeniu czapek.

Ograniczenia

1 ≤ N ≤ 10⁶, 1 ≤ A_i ≤ 10⁹.

Podzadania

Przykład

6
7 7 8 8 9 9

3

5
1 2 3 4 5

5

5
1 1 1 1 1

1

Wielkimi krokami zbliżają się Mistrzostwa Świata w Piłce Nożnej. Aby wyłonić absolutnie najlepszych z najlepszych, organizatorzy postanowili zorganizować w Bajtogrodzie prestiżowy, pokazowy Turniej Gwiazd. Wezmą w nim udział wyłącznie reprezentanci trzech krajów uznawanych za głównych faworytów do złota: Hiszpanii, Francji oraz Anglii.

Z każdego z tych państw na zgrupowanie w Bajtogrodzie przyjechało dokładnie N zawodników. Każdy piłkarz został szczegółowo przebadany, a jego aktualną formę opisano za pomocą współczynnika siły. Zawodnicy z Hiszpanii mają siły opisane ciągiem A = (A₁,A₂,…,A_N), z Francji ciągiem B = (B₁,B₂,…,B_N), natomiast z Anglii – ciągiem C = (C₁,C₂,…,C_N).

Selekcjonerem gospodarzy został legendarny Bajtazar. Jego zadaniem jest stworzenie trzyosobowej drużyny marzeń. Zasady rekrutacji są jednak rygorystyczne: W skład każdej drużyny musi wejść dokładnie jeden gracz z Hiszpanii, jeden z Francji oraz jeden z Anglii. Ponieważ jest to turniej pokazowy, różni selekcjonerzy mogą powoływać tych samych zawodników, jednak żadne dwa zespoły nie mogą mieć identycznego składu. Oznacza to, że każda drużyna jest jednoznacznie wyznaczona przez trójkę indeksów (i, j, k).

Analitycy Bajtazara odkryli, że z powodu specyfiki taktycznej, całkowita siła drużyny składającej się z zawodników o siłach A_i, B_j oraz C_k wyraża się specjalnym, “synergicznym” wzorem: A_iB_j + B_jC_k + C_kA_i.

Wybór drużyn odbywa się w systemie kolejkowym. Przed Bajtazarem swoje składy zarejestrowało już K − 1 innych trenerów. Każdy z nich wybierał drużynę o absolutnie największej możliwej sile spośród jeszcze dostępnych kombinacji.

Bajtazar podchodzi do stolika sędziowskiego jako K-ty w kolejce. Pomóż utytułowanemu selekcjonerowi i oblicz, jaką maksymalną siłę będzie miała drużyna, którą przyjdzie mu sformować.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N oraz K. W drugim wierszu znajduje się N liczb całkowitych A₁, A₂, …, A_N. W trzecim wierszu znajduje się N liczb całkowitych B₁, B₂, …, B_N. W czwartym wierszu znajduje się N liczb całkowitych C₁, C₂, …, C_N.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – maksymalna siła drużyny Bajtazara.

Ograniczenia

1 ≤ N ≤ 2 ⋅ 10⁵, 1 ≤ K ≤ min (N ³,5⋅10⁵), 1 ≤ A_i, B_j, C_k ≤ 10⁹.

Podzadania

Przykład

2 5
1 2
3 4
5 6

31

3 10
100 100 100
100 100 100
100 100 100

30000

5 54
800516877 573289179 26509423 168629803 696409999
656737335 915059758 201458890 931198638 185928366
140174496 254538849 830992027 305186313 322164559

689589940713840351

Farmer Dżon, który właśnie przeszedł na emeryturę, wreszcie ma dużo czasu, by zająć się swoją największą pasją – hodowlą szczurów. Niestety życie emeryta nie jest łatwe: zapasy paszy powoli się kończą, a jego podopieczni robią się coraz bardziej głodni.

Pewnego dnia Dżon znalazł na strychu stary, mocno postrzępiony dywan. Ku jego zaskoczeniu okazało się, że materiał, z którego został wykonany, jest prawdziwym przysmakiem dla szczurów. Problem polega jednak na tym, że nie każdy szczur jest w stanie zjeść dowolny fragment dywanu.

Dywan ma kształt prostokąta o wymiarach N × M i został podzielony na N ⋅ M kwadratów jednostkowych. Pole znajdujące się w wierszu i i kolumnie j ma grubość a_i, j.

Dla szczura o rozmiarze k obowiązują następujące zasady:

• jeśli a_i, j < k, szczur może swobodnie przejść przez dane pole, ale niczego nie zjada,
• jeśli a_i, j > 2k, pole jest zbyt grube i szczur nigdy na nie nie wejdzie,
• jeśli k ≤ a_i, j ≤ 2k, szczur może wejść na pole i zjeść a_i, j − k jednostek dywanu, redukując grubość dywanu w tym kwadracie do k.

Szczur rozpoczyna swoją wędrówkę poza dywanem. Może poruszać się pomiędzy sąsiednimi polami (góra, dół, lewo, prawo), a także dowolnie opuszczać dywan i wracać na niego w innym miejscu na brzegu. Może dowolnie wiele razy wchodzić na to samo pole, jednak po pierwszym wejściu grubość dywanu może być już zmieniona.

Farmer Dżon ma w hodowli Q szczurów i na razie nie wpuszcza żadnego z nich na dywan, ale chciałby wiedzieć ile maksymalnie jednostek dywanu mógłby zjeść każdy ze szczurów, gdyby został wpuszczony.

Wejście

W pierwszym wierszu znajduje się liczba zestawów testowych T. Opis zestawu testowego składa się z następujących wierszy:

• pierwszy wiersz zawiera dwie liczby całkowite N, M,
• kolejne N wierszy zawiera po M liczb całkowitych a_i, j opisujących grubości pól dywanu,
• następny wiersz zawiera liczbę szczurów Q,
• ostatni wiersz zawiera Q liczb k₁, k₂, …, k_Q, oznaczających rozmiary szczurów.

Wyjście

Dla każdego zestawu danych wypisz jeden wiersz zawierający Q liczb – maksymalną liczbę jednostek dywanu, które mógłby zjeść szczur o odpowiednim rozmiarze, gdyby został wpuszczony na dywan.

Ograniczenia

1 ≤ T ≤ 10⁴, 1 ≤ N ⋅ M ≤ 10⁶, 1 ≤ Q ≤ 10⁶, 1 ≤ a_i, j, k_i ≤ 10⁹.

Łączna liczba pól we wszystkich zestawach danych nie przekracza 10⁶.

Łączna liczba szczurów we wszystkich zestawach danych nie przekracza 10⁶.

Podzadania

Przykład

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

2 1 4 14 4 

2
3 3
9 9 9 
9 6 9 
9 9 9 
2
3 5 
1 1
10 
3
4 9 10 

0 33 
0 1 0 

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

13 4 0 27 32 4 32 37 13 
5 0 0 40 39 14 
14 0 19 50 52