Dört Sayı#13072

Dört Sayı

2 saniye
256 megabayt

Olenka'nın tam sayıdan oluşan bir a_1, a_2, \ldots, a_n dizisi ve bir tam sayısı var.

O, a_i + a_j + a_k + a_t \le m olacak şekilde dört indis i, j, k, t (1 \le i, j, k, t \le n) seçmek istiyor. İndislerin farklı olmasının gerekmediğine dikkat edin (bazıları çakışabilir).

Böyle tüm dörtlüler arasında Olenka a_i + a_j + a_k + a_t toplamının mümkün olan en büyük değeriyle ilgileniyor. Bu değeri bulmasına yardım edin veya böyle bir indis dörtlüsünün var olmadığını bildirin.

Giriş

İlk satırda iki tam sayı ve verilir (1 \le n \le 3000, -4 \cdot 10^{18} \le m \le 4 \cdot 10^{18}).

İkinci satırda tam sayı a_1, a_2, \ldots, a_n verilir (-10^{18} \le a_i \le 10^{18}).

Çıktı

Tek bir tam sayı yazdırın — a_i + a_j + a_k + a_t \le m koşulunu sağlayan tüm indis dörtlüleri arasında a_i + a_j + a_k + a_t toplamının en büyük değeri.

Böyle bir dörtlü yoksa yazdırın.

Örnekler

Örnek 1

Loading
Loading

Örnek 2

Loading
Loading

Örnek 3

Loading
Loading

Not

Birinci örnekte i = j = 2 ve k = t = 3 alınabilir: a_2 + a_2 + a_3 + a_3 = 9 + 9 + 1 + 1 = 20 \le 20.

İkinci örnekte mümkün olan en küçük toplam olan a_2 + a_2 + a_2 + a_2 = -8 bile m = -10 değerinden büyüktür, bu yüzden cevap yoktur.

Üçüncü örnekte optimal seçimlerden biri i = 1, j = k = 2, t = 4 şeklindedir: (-5) + 4 + 4 + (-1) = 2.