trang chủ / bài tập / vertbook

Kệ sách của Shaass

Bạn có $n$ cuốn sách. Cuốn sách thứ $i$ có độ dày $t_{i}$ và bề rộng trang $w_{i}$ . Độ dày của mỗi cuốn chỉ có thể là $1$ hoặc $2$ . Tất cả các cuốn sách có cùng chiều cao trang.

Bạn xếp sách lên kệ theo cách sau: chọn ra một số cuốn và đặt chúng thẳng đứng, các cuốn còn lại đặt nằm ngang phía trên những cuốn đứng. Điều kiện là tổng bề rộng của các cuốn nằm ngang không được vượt quá tổng độ dày của các cuốn đứng.

Hãy tìm tổng độ dày nhỏ nhất của các cuốn sách đặt thẳng đứng.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ .
$n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $t_{i}$ và $w_{i}$ .

Dữ liệu ra

Một số nguyên duy nhất: tổng độ dày nhỏ nhất của các cuốn sách đặt thẳng đứng.

Ràng buộc

$1 \leq n \leq 100$
$1 \leq t_{i} \leq 2$
$1 \leq w_{i} \leq 100$

Ví dụ

Input	Output	Giải thích
5 1 12 1 3 2 15 2 5 2 1	5	Đặt đứng các cuốn $1, 3, 4$ với tổng độ dày $1 + 2 + 2 = 5$ . Các cuốn còn lại là $2$ và $5$ , tổng bề rộng $3 + 1 = 4 \leq 5$ . Không thể đạt tổng độ dày $4$ hay nhỏ hơn.
3 1 10 2 1 2 4	3	Đặt đứng các cuốn $1, 3$ với tổng độ dày $1 + 2 = 3$ ; cuốn $2$ nằm ngang có bề rộng $1 \leq 3$ . Lưu ý cách chọn cuốn $1, 2$ cũng có tổng độ dày $3$ nhưng không hợp lệ vì cuốn $3$ nằm ngang có bề rộng $4 > 3$ .
3 2 5 2 5 2 5	6	Nếu đặt đứng hai cuốn thì tổng độ dày là $4$ , trong khi cuốn nằm ngang còn lại có bề rộng $5 > 4$ . Vì vậy phải đặt đứng cả ba cuốn, tổng độ dày $6$ .

Bình luận

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

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 5,00một phần

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

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

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig