Maximize revenue by choosing one query type

You are given a virtual warehouse that can execute queries. There are n query types, and you must choose exactly one query type to run repeatedly for at most k minutes.

For query type i:

• Each run takes time[i] minutes (a positive integer).
• Each run yields profit[i] revenue (a non-negative integer).
• You may run the chosen query type any number of times back-to-back as long as total time does not exceed k .

Task

Return:

1. The maximum total revenue achievable within k minutes.
2. The chosen query type index (0-based) that achieves this maximum.

If multiple query types yield the same maximum revenue, return the smallest index.

Input

• Integer k
• Arrays time[0..n-1] , profit[0..n-1]

Output

• (maxRevenue, bestIndex)

Constraints (typical)

• 1 <= n <= 2e5
• 1 <= k <= 1e18
• 1 <= time[i] <= 1e18
• 0 <= profit[i] <= 1e18

Notes

The chosen query type can be run floor(k / time[i]) times.