1985F - Final Boss - CodeForces Solution

import sys
import bisect
from collections import deque
from heapq import heappop, heappush

def solve(h, n, a, c):
    v = list(zip(a, c))
    v.sort()

    lo, hi = 1, 1000000000000000000
    mx = hi

    while lo <= hi:
        d = (lo + hi) // 2
        health = 0
        for attack, cost in v:
            cnt = 1 + (d - 1) // cost
            health += cnt * attack
            if health >= h:
                break

        if health >= h:
            mx = min(mx, d)
            hi = d - 1
        else:
            lo = d + 1

    return mx

def main():
    input = sys.stdin.read
    data = input().split()
    index = 0

    t = int(data[index])
    index += 1

    results = []
    for _ in range(t):
        h = int(data[index])
        n = int(data[index + 1])
        index += 2
        a = list(map(int, data[index:index + n]))
        index += n
        c = list(map(int, data[index:index + n]))
        index += n

        result = solve(h, n, a, c)
        results.append(result)

    for result in results:
        print(result)

if __name__ == "__main__":
    main()