$n$ қала бар. Әрбір $i$ қаласы үшін біз мән береміз және құнын төлейміз: не мән $0$ болып, $p_i$ тиын төлейміз, не мән $1$ болып, $q_i$ тиын төлейміз.
Сонымен қатар $m$ шектеу берілген. Әр шектеу $[\ell, r]$ кесіндісімен және $a$ мен $b$ екі айыппұлымен анықталады. Егер $\ell$-ден $r$-ге дейінгі (шеткі нүктелерін қоса алғанда) қалалардың арасында мәні $0$ болатын кемінде бір қала болса, біз $a$ тиын айыппұл төлейміз. Егер олардың арасында мәні $1$ болатын кемінде бір қала болса, біз $b$ тиын айыппұл төлейміз. Екі айыппұл бір-біріне тәуелсіз: егер $0$ де, $1$ де кездессе, біз $a + b$ тиын төлейміз.
Қалаларға мән таңдаудың барлық тәсілдерінің ішінен ең аз жалпы шығынды (құндар мен айыппұлдардың қосындысын) табыңыз.
Кіріс деректер
Бірінші жолда бір бүтін сан $t$ берілген: тесттер саны.
Әрбір тесттің бірінші жолында екі бүтін сан $n$ және $m$ ($1 \le n, m \le 2 \cdot 10^5$) берілген.
Келесі $n$ жолдың әрқайсысында екі бүтін сан $p_i$ және $q_i$ ($1 \le p_i, q_i \le 10^9$) берілген: сәйкесінше $i$ қаласы үшін $0$ және $1$ таңдау құндары.
Келесі $m$ жолдың әрқайсысында төрт бүтін сан $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$) берілген: шектеудің параметрлері.
Барлық тесттер бойынша $n$ мәндерінің қосындысы $2 \cdot 10^5$-нен аспайды.
Барлық тесттер бойынша $m$ мәндерінің қосындысы $2 \cdot 10^5$-нен аспайды.
Шығыс деректер
Әрбір тест үшін бір бүтін санды шығарыңыз: ең аз жалпы шығын.
Мысалдар
Кіріс деректер 1
2 3 2 1 5 5 1 3 3 1 3 10 10 2 2 100 1 1 1 7 8 1 1 1 1
Шығыс деректер 1
20 8