You are given a regular \(N\)-sided polygon. Label one arbitrary side as side \(1\), then label the next sides in clockwise order as side \(2\), \(3\), \(\dots\), \(N\). There are \(A_i\) special points on side \(i\). These points are positioned such that side \(i\) is divided into \(A_i + 1\) segments with equal length.
For instance, suppose that you have a regular \(4\)-sided polygon, i.e., a square. The following illustration shows how the special points are located within each side when \(A = [3, 1, 4, 6]\). The uppermost side is labelled as side \(1\).
You want to create as many non-degenerate triangles as possible while satisfying the following requirements. Each triangle consists of \(3\) distinct special points (not necessarily from different sides) as its corners. Each special point can only become the corner of at most \(1\) triangle. All triangles must not intersect with each other.
Determine the maximum number of non-degenerate triangles that you can create.
A triangle is non-degenerate if it has a positive area.
Note
Explanation for the sample input/output #1
One possible construction which achieves maximum number of non-degenerate triangles can be seen in the following illustration.
Explanation for the sample input/output #2
One possible construction which achieves maximum number of non-degenerate triangles can be seen in the following illustration.
