Mã bài:
valy
Điểm:
1,5 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
64M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Một va ly có thể chứa W đơn vị trọng lượng. Có ~n~ đồ vật mỗi vật có trọng lượng ~A[i]~ và có giá trị ~C[i]~ hỏi lên chọn mỗi loại đồ vật bao nhiêu để xếp vào valy sao cho tổng giá trị của valy là lớn nhất.
Input
Dòng đầu tiên là số ~N~ và ~W~ ~(1 ≤ N, W ≤ 100)~
Dòng thứ ~i~ trong số ~N~ dòng tiếp theo mỗi dòng ghi hai số ~A[i]~ và ~C[i]~ ~(1 ≤ A[i], C[i] ≤ 100)~
Output
Dòng đầu tiên là tổng giá trị lớn nhất tìm được của valy
Các dòng tiếp theo mỗi dòng ghi hai số ~i~ (là số hiệu vật được chọn) ~x~ (là số lượng chọn vật ~i~)
Sample Input
4 10
5 4
1 9
8 90
2 16
Sample Output
108
2 2
3 1
Bình luận