Чотири числа#13072

Чотири числа

2 секунди
256 мегабайтів

Оленка має послідовність із цілих чисел a_1, a_2, \ldots, a_n та ціле число .

Вона хоче вибрати чотири індекси i, j, k, t (1 \le i, j, k, t \le n) такі, що a_i + a_j + a_k + a_t \le m. Зверніть увагу, що індекси не обов'язково різні (деякі з них можуть збігатися).

Серед усіх таких четвірок Оленку цікавить найбільше можливе значення a_i + a_j + a_k + a_t. Допоможіть їй знайти його або повідомте, що жодної такої четвірки індексів не існує.

Вхідні дані

Перший рядок містить два цілі числа та (1 \le n \le 3000, -4 \cdot 10^{18} \le m \le 4 \cdot 10^{18}).

Другий рядок містить цілих чисел a_1, a_2, \ldots, a_n (-10^{18} \le a_i \le 10^{18}).

Вихідні дані

Виведіть одне ціле число — максимальне значення a_i + a_j + a_k + a_t серед усіх четвірок індексів, для яких a_i + a_j + a_k + a_t \le m.

Якщо такої четвірки не існує, виведіть число .

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Примітка

У першому прикладі можна взяти i = j = 2 та k = t = 3: a_2 + a_2 + a_3 + a_3 = 9 + 9 + 1 + 1 = 20 \le 20.

У другому прикладі навіть найменша можлива сума a_2 + a_2 + a_2 + a_2 = -8 більша за m = -10, тож відповіді не існує.

У третьому прикладі одним з оптимальних виборів є i = 1, j = k = 2, t = 4: (-5) + 4 + 4 + (-1) = 2.