Düşmənlər və qılınclar

İnputFile

Birinci sətirdə iki tam ədəd $n$ və $m$ ($1\le n,m\le 10^6$) verilmişdir — müvafiq olaraq qılıncların və düşmənlərin sayı.

Sonrakı $n$ sətirdə hər biri üç tam ədəd $a_i$, $b_i$ və $cos{t}_i$ ($0\le a_i,b_i,cos{t}_i\le 10^9$) göstərilmişdir — $i$-ci qılıncın uzunluğu, kəskinliyi və qiyməti.

Daha sonra gələn $m$ sətirdə hər biri üç tam ədəd $c_j$, $d_j$ və $profi{t}_j$ ($0\le c_j,d_j,profi{t}_j\le 10^9$) verilmişdir — $j$-ci düşmənin zirehinin qalınlığı, möhkəmliyi və mükafatı.

Çıxış verilənləri

Tək bir tam ədəd çıxarın — Kozak Vus'un qazana biləcəyi maksimum karbovanets sayı.

Nümunələr

Qiymətləndirmə

1. ($13$ bal): Hər hansı iki düşmən $(i,j)$ üçün, burada $i\ne j$, ya $c_i>c_j$, ya da $d_i>d_j$, yəni hər iki zireh parametri digərindən pis olmayan düşmən yoxdur; $n,m\le 5000$;

2. ($10$ bal): Hər hansı iki düşmən $(i,j)$ üçün, burada $i\ne j$, ya $c_i>c_j$, ya da $d_i>d_j$, yəni hər iki zireh parametri digərindən pis olmayan düşmən yoxdur; $n,m\le 10^5$;

3. ($13$ bal): Hər hansı iki qılınc $(i,j)$ üçün, burada $i\ne j$, ya $a_i>a_j$, ya da $b_i>b_j$, yəni hər iki hücum parametri digərindən pis olmayan qılınc yoxdur; $n,m\le 5000$;

4. ($10$ bal): Hər hansı iki qılınc $(i,j)$ üçün, burada $i\ne j$, ya $a_i>a_j$, ya da $b_i>b_j$, yəni hər iki hücum parametri digərindən pis olmayan qılınc yoxdur; $n,m\le 10^5$;

5. ($14$ bal): $n,m\le 5000$;

6. ($23$ bal): $n,m\le 10^5$;

7. ($17$ bal): Əlavə məhdudiyyətlər olmadan.