SMARTCOMP - Lựa chọn cấu hình
View as PDFMirko rất say mê với việc thiết kế máy tính cảm ứng, sau rất nhiều năm nghiên cứu Mirko đã thiết kế ra một loại máy tính thông minh rất hợp thời, tuy nhiên để sản phẩm đến được với người tiêu dùng với mức giá phải chăng và chất lượng tốt, Mirko quyết định sử dụng các thiết bị chính của nhà cung cấp có tiếng. Bốn bộ phận chính là: chip, màn hình cảm ứng, bo mạch và vỏ máy. Mỗi bộ phận có ~n~ nhà cung cấp, và mỗi bộ phận của một nhà cung cấp có một điểm đánh giá của các khách hàng (~v_i~) và có giá thành là ~c_i~. Tổng điểm đánh giá của chiếc máy tính bằng tổng điểm đánh giá của 4 bộ phận chính này. Bạn hãy giúp Mirko chọn ra được 4 nhà cung cấp cho 4 bộ phận chính của chiếc máy tính mà tổng điểm đánh giá là lớn nhất mà giá thành không quá ~V~.
Input:
- Dòng thứ nhất chứa ~n~ (2 ≤ ~n~ ≤103) là số nhà cung cấp thiết bị, và ~V~ (2 ≤ ~V~ ≤109) là giới hạn trên của tổng giá thành 4 bộ phận chính.
- Dòng thứ ~k~ tiếp theo (~k~ từ 1 đến 4) chứa ~n~ cặp số nguyên dương (~C_{k1}~, ~V_{k1}~) , (~C_{k2}~, ~V_{k2}~), … , (~C_{kn}~, ~V_{kn}~), (1 ≤ ~V_{ki}~,~C_{ki}~ ≤ 109).
Output: Một số duy nhất là tổng điểm đánh giá lớn nhất của máy tính mà tổng giá thành không quá ~V~ hoặc -1 nếu không tìm được.
Ví dụ
Input
2 10
2 2 3 3
2 2 4 5
2 2 5 8
2 2 6 8
Output
11
Giới hạn:
- 50 % số test có ~N~ <=100
- 50 % số test còn lại có ~N~ <= 1000
Comments
@slayder2_0 Một số duy nhất là tổng điểm đánh giá lớn nhất của máy tính mà tổng giá thành không quá ~V~ hoặc -1 nếu không tìm được. Test case #5 rơi vào trường hợp này nha em!