에어컨 설치하기 (Air Cownditioning II)

농부 존의 농장에 기록적인 무더위가 찾아왔습니다. 존은 소들의 열을 식혀주기 위해 에어컨에 투자하기로 결정했습니다.

농부 존의 소 N마리(1 ≤ N ≤ 20)는 1번부터 100번까지 일직선으로 늘어선 외양간 칸에 살고 있습니다.

i번째 소는 s_i번 칸부터 t_i번 칸까지의 범위를 차지하고 있습니다. 각 소가 차지하는 칸의 범위는 서로 겹치지 않습니다.

소들은 제각각 필요한 냉방 요구 수치가 있습니다. i번째 소는 최소 c_i만큼의 온도가 낮아져야 쾌적함을 느낍니다.

즉, i번째 소가 점유하고 있는 모든 칸의 온도가 최소 c_i만큼 내려가야 합니다.

외양간에는 1번부터 M번까지 M개의 에어컨이 있습니다 (1 ≤ M ≤ 10). i번째 에어컨을 가동하는 데는 m_i만큼의 비용이 들며, a_i번 칸부터 b_i번 칸까지의 온도 범위를 p_i만큼 낮춰줍니다.

에어컨이 커버하는 범위는 서로 겹칠 수 있습니다.

농장을 운영하는 것은 쉽지 않은 일이기에, 존은 예산이 매우 빠듯합니다. 모든 소를 쾌적하게 만들기 위해 존이 지불해야 하는 최소 비용을 구하는 프로그램을 작성하시오.

(단, 모든 에어컨을 가동하면 모든 소가 쾌적해진다는 것이 보장됩니다.)

입력

첫째 줄에 소의 수 N과 에어컨의 수 M이 공백을 사이에 두고 주어진다.

다음 N개의 줄에는 i번째 소의 점유 범위 s_i, t_i와 필요한 냉방 수치 c_i가 주어진다.

다음 M개의 줄에는 i번째 에어컨의 가동 범위 a_i, b_i와 냉방 능력 p_i, 가동 비용 m_i가 주어진다.

(참고: 예제 이외의 모든 테스트 데이터에서 M = 10입니다.)

출력

모든 소의 냉방 요구 조건을 충족시키기 위해 필요한 최소 비용을 출력한다.

제약 조건

1 ≤ N ≤ 20

1 ≤ M ≤ 10

1 ≤ s_i, t_i, a_i, b_i ≤ 100

1 ≤ c_i, p_i ≤ 1,000,000

1 ≤ m_i ≤ 1,000

예제 입력 1

2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5

예제 출력 1

10

출처

USACO 2023 January Contest, Bronze