1592: 干饭时间

小R作为一个资深的干饭人，他每次都会抓紧每一分钟的时间去买所有想吃的东西。

这天小R想买的东西有n种，买这n种东西所需要排队等待的时间分别为a1 ， a2 ， a3 ... an ；

由于，小R又是一个非常懒惰的人，他同一时间最多只会去买两种东西，并且，他需要在买的东西做好之前赶回来，不然他要重新排队购买。

例如，买蛋糕的时间为15min，买饮料的时间为10min，买零食的时间为4min，小R可以去买了蛋糕之后，利用等待的时间去买饮料；虽然买完饮料后，还有5min可以去买零食，但是为了简化问题，小R不会去买零食，而是赶回去等在蛋糕做好之后，他再去买零食，这样，他就省出了单独去买饮料的时间，总时间为15min+4min=19min；


再例如，买蛋糕的时间为15min，买饮料的时间也是15min，当他去买蛋糕时，同时他就不能去买饮料了，因为这样他就不满足在蛋糕做好之前赶回来，所以总时间为30min。

小R是个非常聪明的人，所以他会运用他的智慧，找到买完这些东西要用的最短的时间。

请你计算，聪明的小R买完所有他想吃的东西，所用的最短时间。

一行一个整数n ( n <= 1000 )，代表小R想买的东西的个数。

n个整数a1 ， a2 ， a3 ... an ，均不大于1000；

一行一个整数，代表最短的时间。

5
4 1 5 2 3

9