Fionda#10414
Uno dei lavori in fattoria che il Contadino John detesta di più è il trasporto di grandi quantità di letame di mucca. Per semplificare questo processo, ha escogitato un'idea interessante: invece di trasportare il letame da un punto all'altro con un carrello trainato da un trattore, perché non lanciarlo per via aerea con una gigantesca fionda per letame? (Davvero, cosa potrebbe mai andare storto...)
La fattoria del Contadino John si trova lungo un'unica lunga strada rettilinea, quindi qualsiasi luogo nella fattoria può essere descritto semplicemente dalla sua posizione su questa strada (in pratica, un punto su una retta numerica). Il Contadino John ha costruito n~(1 \le n \le 10^5) fionde. La -esima fionda è descritta da tre numeri interi x_i, y_i e t_i, il che significa che può lanciare il letame dalla posizione x_i alla posizione y_i in sole t_i unità di tempo.
Il Contadino John ha m~(1 \le m \le 10^5) cumuli di letame che devono essere trasportati. Il -esimo cumulo deve essere spostato dalla posizione a_j alla posizione b_j. Trasportare il letame con il trattore per una distanza richiede unità di tempo. Il Contadino John spera di ridurre questo tempo utilizzando, per il trasporto di ogni cumulo, al massimo una fionda. Il tempo che il Contadino John trascorre guidando il trattore senza letame non viene conteggiato.
Per ciascuno degli cumuli di letame, aiuta il Contadino John a determinare il tempo minimo possibile per il trasporto, sapendo che per ogni cumulo si può utilizzare al massimo una fionda.
La prima riga contiene due numeri interi e . Ciascuna delle successive righe descrive una fionda con tre numeri interi x_i, y_i e t_i~(0 \le x_i, y_i, t_i \le 10^9). Ciascuna delle ultime righe descrive un cumulo di letame da spostare, con due numeri interi a_j e b_j~(0 \le a_j, b_j \le 10^9).
Stampa righe, una per ciascun cumulo di letame, con il tempo minimo necessario per trasportarlo.
Esempio 1
Il primo cumulo di letame deve essere spostato dalla posizione alla posizione . Senza usare una fionda, ciò richiede unità di tempo. Tuttavia, utilizzando la prima fionda, serve unità di tempo per trasportare il letame fino alla posizione (il punto di partenza della fionda), unità di tempo per lanciarlo per via aerea fino alla posizione (il punto di arrivo della fionda), e altre unità di tempo per trasportarlo fino alla posizione — per un totale di unità di tempo. Il secondo cumulo conviene trasportarlo senza fionda, mentre il terzo va trasportato utilizzando la seconda fionda.