There are N servers connected in series.

For each server:

• Initial throughput is throughput[i].
• One upgrade increases its throughput by 1.
• One upgrade costs cost[i].

You are given a total budget B.

Since the servers are connected in series, the overall throughput of the system equals the minimum throughput among all servers.

Determine the maximum overall throughput that can be achieved without exceeding the budget.

---

Input Format

• First line contains integer N.
• Second line contains N integers throughput[i].
• Third line contains N integers cost[i].
• Fourth line contains integer B.

---

Output Format

Print one integer — the maximum achievable overall throughput.

---

Constraints

• 1 ≤ N ≤ 2 × 10^5
• 1 ≤ throughput[i] ≤ 10^9
• 1 ≤ cost[i] ≤ 10^9
• 1 ≤ B ≤ 10^18

---

Example

Input

3
3 5 2
2 1 3
10

Output

5

Explanation

To make every server have throughput at least 5:

• Server 1: already 5
• Server 2: upgrade 3 times → cost 3 × 3 = 9
• Server 0: upgrade 2 times → cost 2 × 2 = 4

Target 5 is feasible only if total cost is within budget. Binary searching on the answer gives the maximum feasible throughput.

---