Задача с ШАДа
Даются два массива a1, a2, ..., an и b1, b2, b3. ,,, bm, а также вам дают числа A, B, s. Вы должны выбрать несколько чисел из массива a и b таким образом, чтобы сумма взятых чисел была максимальной, но есть ограничение: За каждое взятое число из массива a вы заплатите A, а за каждое взятое число из массива b заплатите B. Вы хотите получить максимальную сумму взятых чисел, но заплатив не более s.

Например:
a = [4, 3, 1, 2]
b = [1, 1, 5, 6, 6]
A = 3, B = 4
s = 16
Ответ 21. Возьмем число 4 из первого массива и числа 5, 6, 6 из второго массива заплатив 15.

Решение:
В общем случае эта задача о рюкзаке которая решается динамическим программированием, но нам дали специально такие ограничения, которые позволяют решить задачу без дп.
По факту мы хотим взять x максимальных чисел из массива a и y максимальных чисел из массива b, чтобы сумма взятых чисел было максимальным и A*x + B*y <= s.

Сначала решим задачу для x = 0. Для этого достаточно взять y самых больших чисел из массива b, что B * y <= s.

Теперь будем увеличивать число x. При каждом увеличении x мы возьмем самое большое число из массива a, но мы можем столкнуться с ситуацией A * x + B * y > s. В такие моменты мы будем уменьшать число y и выкидывать самые маленькие числа, которые мы успели набрать из массива b - это можно делать двумя указателями.

Таким образом мы рассмотрим все возможные пары (x, y) и для каждой пары найдем максимальную сумму. Среди всех таких сумм стоит вывести максимальную.

Время работы O((n + m) * log(max(n, m))

Псевдокод в комментариях.