에어컨 II

$N$ 그루의 나무가 $1 \ldots 100$ 까지 번호가 매겨져 있는 직선형 화단에 심어져 있습니다. 나무 $i$ 는 각각 화단의 $s_i$부터 $t_i$까지 범위의 구역을 차지하며 나무들이 차지하는 구역은 겹치지 않습니다. 나무 $i$ 는 $c_i$만큼의 온도를 낮춰야 최적의 조건으로 성장하기 때문에 최적의 온도를 만들수 있는 에어컨을 설치하려고 합니다.

화단에는 에어컨 $M$대가 설치되어 있으며 $i$번째 에어컨은 $a_i$부터 $b_i$까지 범위의 구역을 $p_i$ ($1 \leq p_i \leq 10^6$)만큼 냉각시킬 수 있고 $m_i$ 만큼의 요금이 듭니다. 에어컨이 냉방하는 구역은 겹칠 수 있습니다.

모든 나무들의 냉방 조건을 만족시킬 수 있는 최소 금액을 구해주세요

• 첫번째 줄 : $N$ 과 $M$ ($1 \leq N \leq 20$), ($1 \leq M \leq 10$)
• $N$ 개의 나무 정보 : $s_i$, $t_i$, $c_i$
• $M$ 개의 에어컨 정보 :  $a_i$, $b_i$, $p_i$, $m_i$
   

입출력 예시

$N$ 그루의 나무와 $M$ 대의 에어컨이 존재합니다.
먼저 $N$ 그루의 나무의 정보가 나옵니다. ($1 \leq N \leq 20$)

• 첫번째 나무는 1 부터 5 구역을 차지하고 2 만큼의 온도를 낮춰야합니다.
• 두번째 나무는 7부터 9 구역을 차지하고 3만큼의 온도를 낮춰야합니다.
  
  그리고 $M$ 대의 에어컨의 정보가 나옵니다. ($1 \leq M \leq 10$)
• 첫번째 에어컨은 2부터 9구역을 2만큼 냉방시킬 수 있으며 3의 비용이 발생합니다.
• 두번째 에어컨은 1부터 6구역을 2만큼 냉방시킬 수 있으며 8의 비용이 발생합니다.
• 세번째 에어컨은 1부터 2구역을 4만큼 냉방시킬 수 있으며 2의 비용이 발생합니다.
• 네번째 에어컨은 6부터 9구역을 1만큼 냉방시킬 수 있으며 5의 비용이 발생합니다.

모든 나무의 냉방 조건을 만족 시키며 에어컨를 가동하는 최소 금액을 나타내는 단일 정수