Gói Thầu Sửa Đường Lý Sơn

Mô tả

Huyện đảo Lý Sơn nổi tiếng với những cánh đồng tỏi xanh mướt và những bức tường đá bazurt cổ thụ. Nhưng mùa mưa bão vừa qua, nhiều tuyến đường nông thôn trên đảo bị sạt lở, sụt lún nặng nề. Ông Ba — trưởng phòng kinh tế hạ tầng huyện — được giao ngân sách cố định để cấp urgent cho các gói thầu sửa đường.

Trên bàn ông có danh sách n gói thầu, mỗi gói có một giá trị dự toán (tính bằng triệu đồng). Ông Ba muốn chọn đúng hai gói thầu phân biệt sao cho tổng giá trị của chúng gần nhất với ngân sách cho phép, nhằm tận dụng tối đa nguồn vốn mà không lãng phí.

Nếu có nhiều cặp có cùng độ lệch tuyệt đối so với ngân sách, ông sẽ ưu tiên chọn cặp có tổng lớn hơn (dùng được nhiều tiền hơn càng tốt). Hãy giúp ông Ba tìm tổng giá trị của cặp thầu tối ưu đó.

Đầu vào

• n (số nguyên): số lượng gói thầu, 2 ≤ n ≤ 10^5.
• budgets (mảng n số nguyên): giá trị dự toán từng gói thầu, mỗi phần tử |phần tử| ≤ 10^6.
• target (số nguyên): ngân sách mục tiêu, |target| ≤ 2 ⨯ 10^6.

Định dạng STDIN (nếu dùng ngôn ngữ biên dịch):

• Dòng 1: số n.
• Dòng 2: n số nguyên cách nhau bởi khoảng trắng — giá trị các gói thầu.
• Dòng 3: số target.

Đầu ra

• Trả về một số nguyên duy nhất: tổng giá trị của cặp hai gói thầu có độ lệch tuyệt đối nhỏ nhất so với target (ưu tiên tổng lớn hơn khi hòa).

Định dạng STDOUT: In ra số đó trên một dòng.

Ràng buộc

• 2 ≤ n ≤ 10^5.
• |budgets[i]| ≤ 10^6 cho mọi i.
• |target| ≤ 2 ⨯ 10^6.
• Tổng hai phần tử bất kỳ nằm trong [-2 ⨯ 10^6, 2 ⨯ 10^6] — an toàn với số nguyên 64 bit.

Ví dụ

Ví dụ 1:

• Đầu vào: n = 5, budgets = [120, 300, 450, 80, 200], target = 500
• Đầu ra: 500

Giải thích: Sắp xếp mảng ta được [80, 120, 200, 300, 450]. Cặp 300 + 200 = 500 trùng khớp hoàn toàn với ngân sách, độ lệch bằng 0 — không thể tốt hơn.

Ví dụ 2:

• Đầu vào: n = 4, budgets = [100, 200, 300, 400], target = 550
• Đầu ra: 600

Giải thích: Các cặp khả thi: 100+200=300 (lệch 250), 100+300=400 (lệch 150), 100+400=500 (lệch 50), 200+300=500 (lệch 50), 200+400=600 (lệch 50), 300+400=700 (lệch 150). Ba cặp 100+400, 200+300, 200+400 đều lệch 50. Theo quy tắc ưu tiên tổng lớn hơn, ta chọn 600.