NBUT的ACMers今天兴致勃勃的去爬山，但是由于玩的太兴奋，直到天黑也没到山脚下。
这时，前面突然出现一座桥，但是他们只有1个手电筒，而且那座桥一次只能容纳两个人同时过去，超过两个人的话，桥就会塌了。
而且每个人过桥所用的时间也不相同。如果没有手电筒，摸着黑去过桥也会不小心掉下去的。所以快的那个人要等着慢的那个人，而且当两个人拿着手电筒到桥的另一端时，那边的人必须要有一个人拿着手电筒回来。
因为要急着赶回家，所以他们需要尽可能少的时间到达对岸，你能帮他们想想办法吗？

第一行包含一个正整数N(1 <= N <= 1000)表示ACMers的人数。
接下来一行有N个数，每个数代表第Ai个人过桥所花的整数时间Ti(1 <= Ti <= 1000)。

输出一行，表示最短过桥时间。