Minimizing Sail Discount on a Pirate Ship

You are given a pirate ship with N flagpoles. The i-th flagpole has a height of H_i (which means it is divided into H_i unit sections) and will hang exactly A_i sails. Each sail occupies one section and on each flagpole, no two sails can share the same section.

When the wind blows, the arrangement of sails affects the total discounted pushing force of the ship. For any sail placed on some flagpole, its pushing force is discounted by the number of sails at the same height on any flagpole behind it (i.e. with a larger index). In other words, if a sail is placed at a certain height, its discount equals the number of sails positioned at that same height on flagpoles behind it. The total discount is the sum of the discounts over all sails.

Your task is to assign positions (i.e. choose a section from 1 to the height of that flagpole) for each sail on every flagpole such that the total discount is minimized.

Reformulation

Suppose we number the flagpoles from 1 to N (from front to back). For each flagpole i, you must choose A_i distinct sections (from 1 to H_i). For any given section height h, let x_h be the total number of sails placed at height h (across all flagpoles that are tall enough to have this section). Then, the total discount contributed by height h is

$$\frac{x_h \cdot (x_h - 1)}{2}.$$

The problem reduces to choosing nonnegative integers \(x_1,x_2,\ldots,x_m\) (where \(m = \max\{H_1, H_2, \ldots, H_N\}\)) satisfying

$$\sum_{h=1}^m x_h = \sum_{i=1}^N A_i,$$

with the constraint that for each \(h\), \(x_h\) cannot exceed the number of flagpoles with height at least \(h\) (denoted by \(\text{cap}(h)\)). That is,

$$x_h \leq \text{cap}(h) = |\{ i \mid H_i \ge h \}|. $$

Your goal is to minimize the total discount:

$$\text{Total Discount} = \sum_{h=1}^m \frac{x_h (x_h - 1)}{2}. $$

Solve this optimization problem and output the minimal total discount.

inputFormat

The input consists of three lines:

1. The first line contains a single integer N (the number of flagpoles).
2. The second line contains N space‐separated integers: H₁, H₂, ..., H_N, representing the heights of the flagpoles.
3. The third line contains N space‐separated integers: A₁, A₂, ..., A_N, where A_i is the number of sails to be hung on the i-th flagpole. It is guaranteed that \(0 \le A_i \le H_i\).

outputFormat

Output a single integer representing the minimum total discounted pushing force achievable by optimally assigning sail positions.

sample

3
3 3 3
1 1 1

0