Cuatro números#13072

Cuatro números

2 segundos
256 megabytes

Olenka tiene una secuencia de números enteros a_1, a_2, \ldots, a_n y un número entero .

Ella quiere elegir cuatro índices i, j, k, t (1 \le i, j, k, t \le n) tales que a_i + a_j + a_k + a_t \le m. Tenga en cuenta que los índices no son necesariamente distintos (algunos de ellos pueden coincidir).

Entre todas esas cuádruplas, a Olenka le interesa el mayor valor posible de a_i + a_j + a_k + a_t. Ayúdela a encontrarlo o informe que no existe tal cuádrupla de índices.

Entrada

La primera línea contiene dos números enteros y (1 \le n \le 3000, -4 \cdot 10^{18} \le m \le 4 \cdot 10^{18}).

La segunda línea contiene números enteros a_1, a_2, \ldots, a_n (-10^{18} \le a_i \le 10^{18}).

Salida

Imprima un único número entero — el valor máximo de a_i + a_j + a_k + a_t entre todas las cuádruplas de índices para las cuales a_i + a_j + a_k + a_t \le m.

Si no existe tal cuádrupla, imprima .

Ejemplos

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Ejemplo 3

Loading
Loading

Nota

En el primer ejemplo, se pueden tomar i = j = 2 y k = t = 3: a_2 + a_2 + a_3 + a_3 = 9 + 9 + 1 + 1 = 20 \le 20.

En el segundo ejemplo, incluso la menor suma posible a_2 + a_2 + a_2 + a_2 = -8 es mayor que m = -10, por lo que no existe respuesta.

En el tercer ejemplo, una de las elecciones óptimas es i = 1, j = k = 2, t = 4: (-5) + 4 + 4 + (-1) = 2.