高桥君和他的朋友一起露营。

高桥君有两个性能相同的烤肉机。这两个烤肉机可以一起工作。一旦把肉放上了烤肉机，就不能中途把肉拿下来，而且你不能同时在一个烤肉机上烤两块肉，也不能把一块烤肉放在两个烤肉机上。直到肉烤好，你才可以把肉取出来。

总共有N块肉，肉的编号为1~N，烤第i块肉所欲的时间为ti。不计算把肉放进烤肉机和拿出烤肉机的时间。

高桥君是一个肉食爱好者，他要求把所有的肉都烤完，而且因为大家的肚子都饿了，所以让烤肉的时间尽可能的最短。

请你求出烤完这些肉的最短时间。

输入输出格式：

输入： 第一行一个整数N(1≤N≤4）

接下来N行，每行是烤第i块肉的所需的时间ti(1≤ti≤50）。

输出格式：

一行，表示所需的最短的时间。