#P18117. Killer Die

Killer Die

Killer Die

标准输入输出。

你有一个公平的 nn 面骰子,各面的正整数面值为 a1,a2,…,ana_1,a_2,\ldots,a_n。你要设计另一个公平的 mm 面骰子,其正整数面值为 b1,b2,…,bmb_1,b_2,\ldots,b_m。

每个骰子的各面被掷出的概率相同。两个骰子都允许不同面具有相同的面值。

独立地掷两个骰子各一次。只有新骰子的面值严格大于原骰子的面值时,新骰子才获胜;平局不算获胜。

在新骰子的获胜概率**严格大于50%**的条件下,求 b1+b2+⋯+bmb_1+b_2+\cdots+b_m 的最小值。

输入格式

第一行两个整数 n,mn,m,分别表示原骰子和新骰子的面数。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

数据范围:

  • 2≤n≤502\le n\le50;
  • 1≤m≤1091\le m\le10^9;
  • 1≤ai≤1091\le a_i\le10^9。

输出格式

输出一个整数,表示新骰子所有面值之和的最小值。

样例1

6 6
1 2 3 4 5 6
25

一种最优方案为 1,1,2,7,7,71,1,2,7,7,7,总和为25。在36种等概率结果中,它获胜的次数为 0+0+1+6+6+6=19>180+0+1+6+6+6=19>18。

样例2

3 2
1 1 2
4

可选择 2,22,2,它在6种等概率结果中获胜4次。

样例3

4 4
3 7 10 11
29

可选择 1,4,12,121,4,12,12,它在16种等概率结果中获胜 0+1+4+4=9>80+1+4+4=9>8 次。