Sapan#10414

Sapan

2 saniye

128 megabayt

Çok zor

Çiftçi John'un çiftlikteki en sevmediği işlerden biri, büyük miktarda inek gübresini taşımaktır. Bu süreci kolaylaştırmak için ilginç bir fikir ortaya attı: gübreyi bir noktadan diğerine traktöre bağlı bir römorkla taşımak yerine, neden devasa bir gübre sapanı kullanarak havadan fırlatmasın? (Gerçekten, ne yanlış gidebilir ki...)

Çiftçi John'un çiftliği tek bir uzun düz yol boyunca yerleşmiştir, bu yüzden çiftlikteki herhangi bir yer basitçe bu yol üzerindeki konumuyla (aslında sayı doğrusu üzerindeki bir nokta ile) tanımlanabilir. Çiftçi John $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) tane sapan inşa etmiştir. $i$ -inci sapan üç tam sayı $x_{i}$ x_i, $y_{i}$ y_i ve $t_{i}$ t_i ile tanımlanır; bu, gübreyi $x_{i}$ x_i konumundan $y_{i}$ y_i konumuna sadece $t_{i}$ t_i birim zamanda fırlatabileceği anlamına gelir.

Çiftçi John'un taşınması gereken $m (1 \leq m \leq 1 0^{5})$ m~(1 \le m \le 10^5) tane gübre yığını vardır. $j$ -inci yığının $a_{j}$ a_j konumundan $b_{j}$ b_j konumuna taşınması gerekmektedir. Gübreyi traktörle $d$ mesafesinde taşımak $d$ birim zaman alır. Çiftçi John, her yığını taşımak için en fazla bir sapan kullanarak bu süreyi kısaltmayı umuyor. Çiftçi John'un gübresiz traktör gezintilerinde harcadığı zaman hesaba katılmaz.

$m$ gübre yığınının her biri için, her yığın için en fazla bir sapan kullanılabileceği koşulu altında, Çiftçi John'un taşıma için mümkün olan minimum süreyi belirlemesine yardımcı olun.

Giriş

İlk satır iki tam sayı $n$ ve $m$ içerir. Sonraki $n$ satırın her biri, üç tam sayı $x_{i}$ x_i, $y_{i}$ y_i ve $t_{i} (0 \leq x_{i}, y_{i}, t_{i} \leq 1 0^{9})$ t_i~(0 \le x_i, y_i, t_i \le 10^9) ile bir sapanı tanımlar. Son $m$ satırın her biri, taşınması gereken bir gübre yığınını iki tam sayı $a_{j}$ a_j ve $b_{j} (0 \leq a_{j}, b_{j} \leq 1 0^{9})$ b_j~(0 \le a_j, b_j \le 10^9) ile tanımlar.

Çıktı

Her gübre yığını için bir satır olmak üzere $m$ satır yazdırın — bu, onu taşımak için gereken minimum süredir.

Örnekler

Örnek 1

Not

İlk gübre yığınının $1$ konumundan $12$ konumuna taşınması gerekiyor. Sapan kullanılmadan bu işlem $11$ birim zaman alır. Ancak birinci sapan kullanılarak, gübreyi $0$ konumuna (sapanın başlangıç noktası) taşımak için $1$ birim zaman, onu havadan $10$ konumuna (sapanın bitiş noktası) fırlatmak için $1$ birim zaman ve ardından $12$ konumuna taşımak için $2$ birim zaman daha gerekir — toplamda $4$ birim zaman. İkinci yığın sapan kullanılmadan taşınırsa en avantajlı olur, üçüncü yığın ise ikinci sapan kullanılarak taşınmalıdır.