Половинки и потолок

Выберите из списка несколько чисел — возможно, ни одного — так, чтобы их сумма была как можно больше, но не превосходила $s$.

Чисел до 34, поэтому перебрать все наборы нельзя.

В первой строке числа $n$ от $1$ до $34$ и $s$ от $0$ до $4 \cdot 10^{10}$. Во второй — $n$ чисел от $1$ до $10^9$.

Одно число.

Переберите суммы каждой половины отдельно. Отсортируйте суммы первой половины — и для каждой суммы второй ищите двоичным поиском самую большую подходящую. Приём из тридцать первого занятия здесь и пригодится.