The Lowest Readings on the Gain Bench

A test bench has amplifiers with integer gains gains and test signals with integer levels signals. Gains and levels can be negative or zero. Running amplifier i on signal j gives the reading gains[i] * signals[j], and the bench runs every pair once, so it produces len(gains) * len(signals) readings (equal readings are all kept).

Return the sum of the k lowest readings.

Examples

Input:  gains = [2, -3], signals = [4, -1, 5], k = 3
Output: -29
Explanation: the readings are 8, -2, 10, -12, 3, -15. The three lowest are
             -15, -12 and -2.

Input:  gains = [2, -3], signals = [4, -1, 5], k = 6
Output: -8

Constraints

• 1 <= len(gains), len(signals) <= 10**5
• -10**5 <= gains[i], signals[j] <= 10**5
• 1 <= k <= min(len(gains) * len(signals), 2 * 10**5)
• Building all the readings is far too slow for the largest tests.

Goals

• See a huge product table as one sorted sequence per row, never built in full
• Walk each row in the direction that its sign makes increasing
• Merge the rows lazily with a heap holding one entry per row