题目描述

小Z有一个包含 $N+1$ 个元素的数组。他可以进行无限次操作：每次选择一个下标 $i$（$1 \leq i \leq N+1$），如果 $A_i \leq 2 \cdot A_{N+1}$，就可以交换 $A_i$ 和 $A_{N+1}$ 的值。 小Z希望通过若干次操作后，数组前 $N$ 个元素的和尽可能小。请你帮助他找出这个最小可能和。

输入格式

• 第一行包含一个整数 $N$。
• 第二行包含 $N+1$ 个整数 $A_1, A_2, \dots, A_N, A_{N+1}$，表示数组的初始元素。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示前 $N$ 个元素的最小可能和。

输入输出样例

4
5 2 1 2 3

8

样例 $\tt \#1$说明

初始数组为 $[5, 2, 1, 2, 3]$。通过交换第一个元素和最后一个元素（因为 $5 \leq 2 \times 3$），得到数组 $[3, 2, 1, 2, 5]$，前4个元素的和为 $3+2+1+2=8$，这是最小可能和。

3
3 10 30 1

43

样例 $\tt \#2$说明

初始数组为 $[3, 10, 30, 1]$。最后一个元素是1，由于没有元素满足小于等于2倍的最后元素（即2），所以无法进行任何交换。前3个元素的和为 $3+10+30=43$。

4
16 4 8 2 1

15

样例 $\tt \#3$说明

初始时，$A = [16, 4, 8, 2, 1]$。考虑下面的操作序列：

• 选 $i = 4$，合法因为 $2 \leq 2 \cdot 1$。现在 $A = [16, 4, 8, 1, 2]$。
• 选 $i = 2$，合法因为 $4 \leq 2 \cdot 2$。现在 $A = [16, 2, 8, 1, 4]$。
• 选 $i = 3$，合法因为 $8 \leq 2 \cdot 4$。现在 $A = [16, 2, 4, 1, 8]$。
• 选 $i = 1$，合法因为 $16 \leq 2 \cdot 8$。现在 $A = [8, 2, 4, 1, 16]$。

前 $N$ 个元素的和是15，这是最优解。

数据范围

对于$10\%$的数据，满足$n = 1$

对于另外$30 \%$的数据，满足$1\le n \le 1000$

对于$100\%$的数据，满足$1 \leq N \leq 10^{5},1 \leq A_i \leq 1000$