Electric Scooter

hard
A ride-sharing company has nn electric scooters available for a new rental service. You are given two 00-indexed integer arrays, startCosts\texttt{startCosts} and chargeCosts\texttt{chargeCosts}, both of length nn. The ithi^{th} scooter requires startCosts[i]\texttt{startCosts}[i] units of battery charge to start and consumes chargeCosts[i]\texttt{chargeCosts}[i] units of battery per kilometer traveled. You are also given an integer batteryLimit\texttt{batteryLimit} representing the maximum available battery charge for the operation.

When using a consecutive segment of kk scooters, the total battery consumption is calculated as max⁡(startCosts)+k×∑(chargeCosts)\max(\texttt{startCosts}) + k \times \sum(\texttt{chargeCosts}), where max⁡(startCosts)\max(\texttt{startCosts}) is the highest startup charge among the kk scooters and ∑(chargeCosts)\sum(\texttt{chargeCosts}) is the total battery consumption of all kk scooters per kilometer.

Return the maximum number of consecutive scooters you can deploy such that the total battery consumption does not exceed batteryLimit\texttt{batteryLimit}.

Input Format:

The first line of input contains three integers nn (1≤n≤105)(1 \leq n \leq 10^5) denoting the size of startCosts\texttt{startCosts} and chargeCosts\texttt{chargeCosts} and bb (1≤b≤1015)(1 \leq b \leq 10^{15}) denoting batteryLimit\texttt{batteryLimit}.

The second line contains nn integers s1,s2,…,sns_1, s_2, \dots, s_n representing startCosts\texttt{startCosts}. (1≤si≤105)(1 \leq s_i \leq 10^5)

The third line contains nn integers c1,c2,…,cnc_1, c_2, \dots, c_n representing chargeCosts\texttt{chargeCosts}. (1≤ci≤105)(1 \leq c_i \leq 10^5)

Output Format:

Give a single integer representing the answer.

Examples:

Example 1:

Input:

5 25
3 6 1 3 4
2 1 3 4 5

Output:

3

Example 2:

Input:

3 19
11 12 19
10 8 7

Output:

0

Code

Loading Editor...