Максимальная сумма прямоугольника не больше K

Дана числовая матрица matrix и число k. Верните максимальную сумму элементов какого-либо прямоугольного подмассива (несколько подряд идущих строк и подряд идущих столбцов), не превышающую k. Гарантируется, что хотя бы один прямоугольник с суммой ≤ k существует. Подсказка: переберите пару (верхняя, нижняя строка), сожмите матрицу между ними в одномерный массив столбцовых сумм - остаётся классическая подзадача "наибольшая сумма подотрезка ≤ k" через префиксы и бинарный поиск по отсортированным префиксам.