Air Cownditioning II

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nông dân John có $N$ con bò trong chuồng với các ô chuồng đánh số từ $1$ đến $100$ . Con bò thứ $i$ chiếm các ô từ $s_{i}$ đến $t_{i}$ và cần được làm mát ít nhất $c_{i}$ đơn vị. Trang trại có $M$ máy điều hòa. Máy thứ $i$ làm mát các ô từ $a_{i}$ đến $b_{i}$ với công suất $p_{i}$ và chi phí $m_{i}$ .

Hãy tìm chi phí tối thiểu để chạy đủ máy điều hòa sao cho tất cả các con bò đều đạt yêu cầu làm mát.

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ và $M$
$N$ dòng tiếp theo: mỗi dòng chứa $s_{i}$ , $t_{i}$ , $c_{i}$
$M$ dòng tiếp theo: mỗi dòng chứa $a_{i}$ , $b_{i}$ , $p_{i}$ , $m_{i}$

Dữ liệu ra

Một số nguyên duy nhất là chi phí tối thiểu.

Ràng buộc

$1 \leq N \leq 20$ , $1 \leq M \leq 10$
$1 \leq m_{i} \leq 1000$ , $1 \leq p_{i} \leq 10^{6}$
Các phạm vi ô chuồng của bò không giao nhau
Sử dụng tất cả máy điều hòa luôn đảm bảo tất cả bò thoải mái

Ví dụ

Input	Output	Giải thích
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	Sử dụng máy [2,9], [1,2] và [6,9] với chi phí 3 + 2 + 5 = 10.

Bình luận

Không có bình luận tại thời điểm này.