8652번 - Podatki 다국어

Kupiec Bajtazar przybył do Bajtogrodu z zamiarem wzbogacenia się na rynku nieruchomości. Planuje on wykupić fragment zabudowy miasta pod wynajem lokali. Główną bolączką Bajtazara są jednak podatki...

Ulice Bajtogrodu tworzą regularną siatkę. Jest n + 1 ulic biegnących z zachodu na wschód i m + 1 ulic biegnących z południa na północ. Na podstawie płaskiej mapy Bajtogrodu, ulice pierwszego typu będziemy nazywali ulicami poziomymi, a ulice drugiego typu - ulicami pionowymi. Każda ulica pozioma przecina każdą ulicę pionową. W Bajtogrodzie znajduje się zatem n · m kwartałów, czyli obszarów ograniczonych z każdej strony ulicami. Boki każdego kwartału wyrażają się całkowitą liczbą bajtometrów. Kwartał o rozmiarze k × l jest podzielony na k · l lokali mieszkalnych.

Pewnego razu burmistrz Bajtogrodu postanowił wprowadzić podatek gruntowy. Chcąc uprościć mieszkańcom obliczanie podatku, postanowił, że w każdym z n poziomych rzędów kwartałów stawka podatku będzie taka sama. Dokładniej, jeśli w i-tym rzędzie kwartałów (1 ≤ i ≤ n) burmistrz ustalił stawkę podatku a_i, a rząd ten ma wysokość x_i, to każdy lokal mieszkalny w tym rzędzie opłaca podatek równy a_i/x_i. Jeśli w danym rzędzie wiele budynków z lokalami ma charakter zabytkowy, burmistrz zamiast podatku wprowadzał w takim rzędzie dotację na dofinansowanie zabytków wypłacaną z budżetu miasta. Stawka dofinansowania również była stała dla danego rzędu lokali. Tak więc jeśli w danym rzędzie kwartałów obowiązuje podatek, zakładamy, że a_i < 0, a jeśli dofinansowanie, to a_i ≥ 0.

Niestety, burmistrz nie uzgodnił swojego pomysłu z radą miasta, która również wpadła na pomysł wprowadzenia podatku gruntowego. Pech chciał, że rada miasta postanowiła opodatkować kolumny kwartałów, stosując dokładnie tę samą zasadę, co burmistrz (przy stawce podatku b_i w kolumnie o szerokości y_i każdy lokal opłaca podatek b_i/y_i). Rada miasta również brała pod uwagę zabytki i czasem, zamiast podatku, wprowadzała dotację na ich dofinansowanie.

Burmistrz i rada miasta ogłosili swoje uchwały mniej więcej w tym samym czasie. Aby teraz uniknąć politycznych sporów, burmistrz i rada miasta poszli na ugodę. Stawka podatku za dany lokal mieszkalny będzie równa sumie stawek z podatku wprowadzonego przez burmistrza i przez radę miasta.

Bajtazar chciałby zakupić wszystkie lokale mieszkalne położone na pewnym obszarze w kształcie prostokąta. Może on przy tym kupować jedynie całe kwartały. Pomóż mu wyznaczyć obszar, w którym suma dofinansowań i podatków będzie możliwie największa.

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n. Drugi wiersz wejścia zawiera ciąg n liczb całkowitych a_i. Trzeci wiersz wejścia zawiera ciąg x_i liczb całkowitych dodatnich m. Czwarty wiersz wejścia zawiera jedną liczbę całkowitą m. Piąty wiersz wejścia zawiera ciąg m liczb całkowitych b_i. Szósty wiersz wejścia zawiera ciąg m liczb całkowitych dodatnich y_i.

Liczby n oraz m spełniają warunki: 1 ≤ n, m ≤ 200 000. Elementy ciągów a_i oraz b_i spełniają warunki: -10 000 ≤ a_i, b_i ≤ 10 000. Ujemne wartości tych ciągów oznaczają stawkę podatku wprowadzonego, odpowiednio, przez burmistrza i przez radę miasta, natomiast nieujemne wartości oznaczają dotacje na dofinansowanie zabytków. Elementy ciągów x_i oraz y_i (tj. wysokości rzędów i szerokości kolumn kwartałów) spełniają warunki: 1 ≤ x_i, y_i ≤ 10 000.

Twój program powinien wypisać na wyjście jedną liczbę całkowitą - największą sumę dofinansowań i podatków na prostokątnym obszarze kwartałów.

Liczby umieszczone po lewej stronie rysunku przedstawiają stawki podatku w rzędach kwartałów (ciąg a_i), a liczby pod rysunkiem przedstawiają stawki w kolumnach kwartałów (ciąg b_i). Liczba w kwadracie jednostkowym oznacza stawkę podatku w danym kwartale. Zaznaczony prostokąt przedstawia obszar, w jaki powinien zainwestować Bajtazar.