문제
철수는 식물을 기르려고 한다.
1~100으로 번호가 매겨진 화분에 N개의 식물이 심어져있다.
i번째 식물은 si에서 시작하여 ti로 끝나는 범위에 뿌리를 내리고 있으며 ci만큼의 물을 필요로한다.
철수에게는 M개의 자동분무기가 있고, i번째 자동분무기를 가동하는데 필요한 비용은 mi이며, ai에서 bi까지 물을 pi만큼 뿌린다.
물이 뿌려지는 위치는 겹칠 수도 있다.
철수를 위해 식물을 모두 잘 기르기 위해 필요한 최소 비용을 출력하시오.
입력
첫 번째 줄에 N과 M이 공백을 기준으로 입력된다 (1≤N≤20, 1≤M≤10).
두 번째 줄부터 N줄에 걸쳐 si, ti, ci가 입력된다.
그 다음 M줄에는 ai, bi, pi, mi가 입력된다 (1≤mi≤1000, 1≤pi≤106).
예제를 제외한 모든 입력의 M은 10이다.
출력
철수가 식물을 모두 잘 기르기 위해 필요한 최소 비용을 출력하시오.
답이 늘 존재함을 보장한다.
예제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
출력
10
힌트
출처
USACO 2023 January Bronze