SMARTCOMP - Lựa chọn cấu hình - Trường THPT Chuyên Lê Quý Đôn

SMARTCOMP - Lựa chọn cấu hình

Points: 200.00

Time limit: 3.0s

Memory limit: 64M

Input: stdin

Output: stdout

Author:

admin

Problem type

Allowed languages

C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Mirko 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_{k 1}$ , $V_{k 1}$ ) , ( $C_{k 2}$ , $V_{k 2}$ ), … , ( $C_{k n}$ , $V_{k n}$ ), (1 ≤ $V_{k i}$ , $C_{k i}$ ≤ 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

Copy

Output

Copy

Giới hạn:

50 % số test có $N$ <=100
50 % số test còn lại có $N$ <= 1000

Comments

Please read the guidelines before commenting.

6

kieulqd commented 9:59:40 am, 21/12/2020 ← edited →

@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!