파일 업로드

에어컨 II

profile
실행 시간 제한메모리 제한
2 초1024 MB
📃 해결할 문제

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

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

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

💻 입력
  • 첫번째 줄 : NNMM (1N201 \leq N \leq 20), (1M101 \leq M \leq 10)
  • NN 개의 나무 정보 : sis_i, tit_i, cic_i
  • MM 개의 에어컨 정보 :  aia_i, bib_i, pip_i, mim_i
     

입출력 예시

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

  • 첫번째 나무는 1 부터 5 구역을 차지하고 2 만큼의 온도를 낮춰야합니다.
  • 두번째 나무는 7부터 9 구역을 차지하고 3만큼의 온도를 낮춰야합니다.

    그리고 MM 대의 에어컨의 정보가 나옵니다. (1M101 \leq M \leq 10)
  • 첫번째 에어컨은 2부터 9구역을 2만큼 냉방시킬 수 있으며 3의 비용이 발생합니다.
  • 두번째 에어컨은 1부터 6구역을 2만큼 냉방시킬 수 있으며 8의 비용이 발생합니다.
  • 세번째 에어컨은 1부터 2구역을 4만큼 냉방시킬 수 있으며 2의 비용이 발생합니다.
  • 네번째 에어컨은 6부터 9구역을 1만큼 냉방시킬 수 있으며 5의 비용이 발생합니다.
🖨️ 출력

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


💻 예제 입력 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

💡 힌트

최소한의 돈을 들이는 한 가지 가능한 방법 구역 [2,9][2, 9], [1,2][1, 2], 그리고 [6,9][6, 9]를 냉방하는 경우며, 이 경우 비용은 3+2+5=103 + 2 + 5 = 10이 됩니다.


출처: USACO 2023 January Contest, Bronze Problem 2. Air Cownditioning II