Dörd ədəd#13072

Dörd ədəd

2 saniyə
256 meqabayt

Olenkanın tam ədəddən ibarət a_1, a_2, \ldots, a_n ardıcıllığı və tam ədədi var.

O, elə dörd i, j, k, t (1 \le i, j, k, t \le n) indeksi seçmək istəyir ki, a_i + a_j + a_k + a_t \le m olsun. Nəzərə alın ki, indekslərin fərqli olması vacib deyil (onlardan bəziləri üst-üstə düşə bilər).

Belə dördlüklərin hamısı arasında Olenkanı a_i + a_j + a_k + a_t cəminin mümkün olan ən böyük qiyməti maraqlandırır. Ona bu qiyməti tapmağa kömək edin və ya belə indekslər dördlüyünün mövcud olmadığını bildirin.

Giriş

Birinci sətirdə iki tam ədəd və verilir (1 \le n \le 3000, -4 \cdot 10^{18} \le m \le 4 \cdot 10^{18}).

İkinci sətirdə tam ədəd a_1, a_2, \ldots, a_n verilir (-10^{18} \le a_i \le 10^{18}).

Çıxış

Bir tam ədəd — a_i + a_j + a_k + a_t \le m şərtini ödəyən bütün indeks dördlükləri arasında a_i + a_j + a_k + a_t cəminin maksimal qiymətini çap edin.

Əgər belə dördlük mövcud deyilsə, çap edin.

Nümunələr

Nümunə 1

Loading
Loading

Nümunə 2

Loading
Loading

Nümunə 3

Loading
Loading

Qeyd

Birinci nümunədə i = j = 2 və k = t = 3 götürmək olar: a_2 + a_2 + a_3 + a_3 = 9 + 9 + 1 + 1 = 20 \le 20.

İkinci nümunədə mümkün olan ən kiçik cəm olan a_2 + a_2 + a_2 + a_2 = -8 belə m = -10 qiymətindən böyükdür, ona görə də cavab yoxdur.

Üçüncü nümunədə optimal seçimlərdən biri i = 1, j = k = 2, t = 4-dür: (-5) + 4 + 4 + (-1) = 2.