Choose the Optimal Network Retry Threshold

Problem: Choose the Optimal Network Retry Threshold Apple Music may experience network fluctuations during playback. The system must decide how many times it should retry a network request. Retrying may recover from a temporary network hiccup, but excessive retries waste battery if the network is truly down. You are given historical logs. Each record has two columns: retry_count: the retry attempt on which the session recovered; if the session failed, it is the number of retries observed/attempted. is_success: whether the session eventually recovered, where 1 means success and 0 means failure. Choose a global threshold T: The system retries at most T times. If a successful sample has retry_count <= T, that session is considered recovered and earns benefit B. Each retry costs battery cost C. For one log record, under threshold T, its retry cost is C * min(retry_count, T). The total utility is: utility(T) = B * number of recovered sessions - C * total number of retries across all sessions Return the smallest threshold T that maximizes total utility. T = 0 is allowed, meaning no retries. Input Format n B C retry_count_1 is_success_1 retry_count_2 is_success_2 ... retry_count_n is_success_n Output Format T Constraints 1 <= n <= 2 * 10^5 1 <= retry_count_i <= 10^9 is_success_i is either 0 or 1 1 <= B, C <= 10^9 If multiple thresholds have the same utility, return the smallest one. Example Input: 5 100 10 1 1 2 1 3 1 5 0 5 0 Output: 3 Example Input 5 100 10 1 1 2 1 3 1 5 0 5 0 Output 3