0 Judge
Code: 0
有一個陣列$a[1]\cdots a[N]$。現在要選擇其中的一些數，相鄰的有選到的數會形成一組，例如選了$a[2],a[3],a[4],a[5],a[7],a[10],a[11]$，會形成三組。請問所有選法當中，「選到的數的總和」乘以「組數」的最大值是多少？
第一行有一個正整數$N$。($1\leq N \leq 2000$)
第二行有$N$個正整數$a[1]\cdots a[N]$。($1\leq a[i] \leq 1000$)
所有選法當中，「選到的數的總和」乘以「組數」的最大值。
子任務一(10%)：$1\leq N \leq 3$
子任務二(30%)：$1\leq N \leq 17$
子任務三(60%)：無特別限制
5
3 1 2 4 4275
3 1 2 5 42817
3 3 2 4 1 7 4 5 2 3 1 6 2 1 5 3 3328範例1：選擇$a[1],a[3],a[5]$，共形成三組，相乘為$9\times 3=27$。
範例2：選擇$a[1],a[3],a[4],a[5]$，共形成兩組，相乘為$14\times 2=28$。
範例3：唯一的最佳方案是選擇$a[1],a[2],a[4],a[6],a[8],a[10],a[12],a[13],a[15],a[17]$。