# Maximum Bottleneck Throughput
## Problem Statement
You are given $n$ services, where the $i$-th service provides input to the $(i+1)$-th service. Each service $i$ has an initial throughput $T_i$ and a cost $C_i$ to scale it once. The overall throughput of the system is limited by the service with the minimum throughput, which is known as the bottleneck.
When a service $i$ is scaled, its original throughput $T_i$ is added to its current throughput. For example, if a service has an initial throughput of $4$ and is scaled twice, its throughput increases from $4$ to $8$ (after one scale) and then from $8$ to $12$ (after a second scale). If service $i$ is scaled $k_i$ times, its new throughput becomes $T_i \cdot (k_i+1)$. Each scaling operation for service $i$ costs $C_i$. Thus, scaling service $i$ a total of $k_i$ times costs $k_i \cdot C_i$.
You are given a total budget $B$. Your goal is to determine the maximum possible bottleneck throughput that can be achieved by optimally scaling the services within the given budget. You can choose to scale any service $i$ any non-negative integer number of times, $k_i \ge 0$.
Formally, you need to find the maximum value $X$ such that there exist non-negative integers $k_1, k_2, \dots, k_n$ satisfying:
1. For all $i \in [1, n]$, the scaled throughput $T_i \cdot (k_i+1) \ge X$.
2. The total cost $\sum_{i=1}^n k_i \cdot C_i \le B$.
## Input Format
- The first line contains a single integer $n$ ($1 \le n \le 10^5$), the number of services.
- The second line contains $n$ integers $T_1, T_2, \dots, T_n$ ($1 \le T_i \le 10^9$), representing the initial throughputs of the services.
- The third line contains $n$ integers $C_1, C_2, \dots, C_n$ ($1 \le C_i \le 10^9$), representing the cost to scale each service once.
- The fourth line contains a single integer $B$ ($0 \le B \le 10^{9}$), the total budget.
## Output Format
A single integer representing the maximum possible bottleneck throughput.
## Sample Test Cases
### Sample Input 1
```
3
4 2 7
3 5 6
32
```
### Sample Output 1
```
10
```
### Sample Input 2
```
2
100 100
1 100
50
```
### Sample Output 2
```
100
```
## Constraints
- $1 \le n \le 10^5$
- $1 \le T_i \le 10^9$
- $1 \le C_i \le 10^9$
- $0 \le B \le 10^{9}$
- Time limit: 1 second
- Memory limit: 256 MB
## Explanation
### Sample 1
Given $n=3$, initial throughputs $T=[4, 2, 7]$, scaling costs $C=[3, 5, 6]$, and budget $B=32$.
We want to find the maximum $X$ such that we can achieve throughputs of at least $X$ for all services with a total cost not exceeding $B$.
Let's try to achieve a bottleneck throughput of $X=10$:
- For service 1 ($T_1=4, C_1=3$): We need $4 \cdot (k_1+1) \ge 10 \implies k_1+1 \ge 2.5$. The smallest integer $k_1+1$ is $3$, so $k_1=2$. Cost: $2 \cdot 3 = 6$. New throughput: $4 \cdot 3 = 12$.
- For service 2 ($T_2=2, C_2=5$): We need $2 \cdot (k_2+1) \ge 10 \implies k_2+1 \ge 5$. The smallest integer $k_2+1$ is $5$, so $k_2=4$. Cost: $4 \cdot 5 = 20$. New throughput: $2 \cdot 5 = 10$.
- For service 3 ($T_3=7, C_3=6$): We need $7 \cdot (k_3+1) \ge 10 \implies k_3+1 \ge 1.42...$. The smallest integer $k_3+1$ is $2$, so $k_3=1$. Cost: $1 \cdot 6 = 6$. New throughput: $7 \cdot 2 = 14$.
The total cost for $X=10$ is $6 + 20 + 6 = 32$. This is exactly equal to the budget $B=32$. All services achieve at least $10$ throughput (specifically $12, 10, 14$). Thus, $X=10$ is achievable.
Now, let's try to achieve a bottleneck throughput of $X=11$:
- For service 1 ($T_1=4, C_1=3$): We need $4 \cdot (k_1+1) \ge 11 \implies k_1+1 \ge 2.75$. Smallest integer $k_1+1=3$, so $k_1=2$. Cost: $2 \cdot 3 = 6$. New throughput: $12$.
- For service 2 ($T_2=2, C_2=5$): We need $2 \cdot (k_2+1) \ge 11 \implies k_2+1 \ge 5.5$. Smallest integer $k_2+1=6$, so $k_2=5$. Cost: $5 \cdot 5 = 25$. New throughput: $12$.
- For service 3 ($T_3=7, C_3=6$): We need $7 \cdot (k_3+1) \ge 11 \implies k_3+1 \ge 1.57...$. Smallest integer $k_3+1=2$, so $k_3=1$. Cost: $1 \cdot 6 = 6$. New throughput: $14$.
The total cost for $X=11$ is $6 + 25 + 6 = 37$. This exceeds the budget $B=32$. Thus, $X=11$ is not achievable.
Since $10$ is achievable and $11$ is not, the maximum bottleneck throughput is $10$.
Loading problem statement...