There are villages, numbered from to . Initially, these villages are all isolated.

Now, these villages want to establish some **bi-directional** roads to achieve interconnection.

Building a road requires a certain cost. Specifically, building a bi-directional road between village and village costs . The construction of a bi-directional road will be completed jointly by the two villages connected by this road. However, the human resources that each village can provide are limited. Village can participate in the construction of at most roads. In other words, there can be at most roads that have village as one endpoint.

What is the minimum cost to make all villages reachable to each other via roads?

The first line contains an integer , denoting the number of villages.

The second line contains  integers , where  denotes the maximum number of roads that village  can participate in building.

Output a single integer, which is the minimum cost  to make all  villages reachable to each other via roads.

If it is impossible, then output "-1".

3
2 2 2

15

3
1 1 1

-1

For the first example, the built roads are  and . Thus the cost is .

For the second example, it is easy to verify that it is impossible to connect all three villages anyway.