Giá sách (Dễ)

Đ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

Có $N$ quyển sách cần xếp theo thứ tự lên các kệ, mỗi kệ có chiều rộng tối đa $L$ . Chiều cao của một kệ bằng chiều cao quyển sách cao nhất trên kệ đó. Tổng chiều cao = tổng chiều cao của tất cả các kệ.

Tối thiểu hóa tổng chiều cao.

Dữ liệu vào

Dòng $1$ : Hai số nguyên $N$ và $L$ .
$N$ dòng tiếp: $H_{i}$ và $W_{i}$ — chiều cao và chiều rộng của sách thứ $i$ .

Dữ liệu ra

Một số nguyên — tổng chiều cao tối thiểu.

Ràng buộc

$1 \leq N \leq 2000$
$1 \leq L \leq 10^{9}$
$1 \leq H_{i} \leq 10^{6}$
$1 \leq W_{i} \leq L$

Ví dụ

Input	Output	Giải thích
5 10 5 7 9 2 8 5 13 2 3 8	21	Kệ 1: sách 1 (h=5, w=7). Kệ 2: sách 2,3,4 (h=13, w=9). Kệ 3: sách 5 (h=3, w=8). Tổng=21.

Bình luận

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