JOI 2015 - Treasures
Xem PDF
Điểm:
1800 (p)
Thời gian:
10.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
Anna và Bruno tìm thấy \(N\) báu vật. Mỗi vật có giá thị trường \(X_i\) và độ quý hiếm \(Y_i\). Mỗi vật có thể được Anna lấy, Bruno lấy, hoặc để lại; không thể thuộc cả hai.
Anna hài lòng nếu trị tuyệt đối hiệu tổng giá thị trường hai người lấy không quá \(D\). Trong các cách làm Anna hài lòng, hãy tối đa hóa tổng độ quý hiếm của Bruno trừ tổng độ quý hiếm của Anna.
Dữ liệu vào
Dòng đầu chứa \(N,D\). Mỗi trong \(N\) dòng sau chứa \(X_i,Y_i\).
Dữ liệu ra
In giá trị lớn nhất có thể.
Ràng buộc
\[
1\le N\le30,\qquad 0\le D\le10^{15},
\]
\[
0\le X_i,Y_i\le10^{15}.
\]
Trong bộ dữ liệu 1, \(N\le10\). Trong bộ dữ liệu 2, \(D=0\).
Ví dụ
Ví dụ 1
Input
6 15
50 900
30 200
40 100
80 600
60 100
70 700Output
1200Giải thích
Ở ví dụ 1, Anna lấy các vật 2, 3, 5 và Bruno lấy 1, 6. Hiệu giá thị trường là \(10\le15\) và hiệu độ quý hiếm là \(1600-400=1200\).
Ví dụ 2
Input
5 0
0 1000000000000000
0 1000000000000000
1 1
1000000000000000 0
1000000000000000 0Output
2000000000000000Kỳ thi:
- JOI 2015/2015 - Vòng sơ khảo (1 Tháng 1., 2015)
Bình luận