Allenamento per la maratona

Nota storica: in pochi sanno che Turing era un patito maratoneta, a tal punto che il suo record personale, ottenuto il 25 agosto del 1947, 2 ore e 46 minuti e 3 secondi, e stato di soli 11 minuti superiore a quello del vincitore delle Olimpiadi del 1948 (l’argentino Delfo Cabrera, che vinse in 2 ore, 34 minuti e 51 secondi).

Alan Turing si vuole allenare per la maratona.
Il suo problema e quello di rifornirsi d’acqua.
Ha una mappa piuttosto accurata della zona, con segnate tutte le fontanelle disponibili, e sulla quale ha riportato il percorso che intende fare.
Ha scelto un percorso formato solo da tratti in direzione orizzontale (Est-Ovest) o verticale (Nord-Sud).
Turing, per semplicità, consuma 1 ml di acqua per a ogni metro che corre: dopo aver bevuto 100 ml, per esempio, è in grado di correre per 100 m.
Turing pero non vuole bere mai più di 100 ml per volta, e vuole correre senza essere appesantito: quindi, vuole portarsi appresso una borraccia più piccola possibile.
Data la mappa con segnate le fontanelle, aiutate Turing a capire qual è la capacità della più piccola borraccia che gli consente di correre avendo sempre acqua a sufficienza.

Considerate l’esempio mostrato in figura, dove l’origine degli assi (0, 0) e in basso a sinistra: qui Turing parte dal punto di coordinate (0, 400) (marcato da una P) e corre lungo 7 tratti lunghi, in ordine, rispettivamente 300, 400, 300, 700, 200, 200 e 400 metri.
Ci sono due fontanelle nel percorso, la prima (marcata come F1) nel punto di coordinate (300, 100) e la seconda (marcata come F2) nel punto di coordinate (600, 500).
Per questo percorso, Turing ha bisogno di una borraccia da 800 ml: infatti, partendo con la borraccia piena, incontra la prima fontanella dopo 600 m.
Qui Turing beve (100 ml), e riempie la borraccia (800 ml), cosa che gli fornisce l’autonomia per raggiungere la seconda fontanella, che dista 900 m nel percorso da lui seguito.
A questo punto, seguendo il suo percorso, passa nuovamente per la seconda fontanella dopo 800 m, e da qui gli mancano solo 200 m per l’arrivo.
Come si vede, una borraccia da 800 ml gli è sufficiente per potersi allenare in questo percorso.

Si assume che Turing parte sempre con la borraccia e la pancia piena.
Nota bene: Turing, oltre a riempire la borraccia, quando arriva a una fontanella può bere e, in ogni istante, Turing può avere al massimo 100 ml in pancia: per esempio, se beve 100 ml a una fontana e dopo 20 m incontra un’altra fontana, a questa può bere solo 20 ml.

Dati in Input

Il file di input consiste di N+M+2 righe.
La prima riga contiene due interi N ed M, rispettivamente il numero di tratti in cui il suo percorso è suddiviso, e il numero di fontanelle presenti nella zona.
Le successive N+1 righe contengono ciascuna due interi Xi, Yi, le coordinate (in metri) dell’i-esimo vertice del percorso di Turing.
Le ultime M righe contengono ciascuna due interi Sx, Sy, le coordinate (in metri) delle fontanelle.
L’istanza mostrata nel file di esempio si riferisce a quella mostrata in figura.

Dati in Output

Il file di output consiste di un unica riga contente un unico intero T: la capacità in ml della borraccia che Turing dovrà comprare per poter completare il suo percorso utilizzando solo i rifornimenti lungo di esso.

Assunzioni

• 1 ≤ N, M ≤ 100000
• 1 ≤ Xi , Yi , Sx , Sy ≤ 10⁹
• 1 ≤ T ≤ 10⁹

Esempi