题目描述
巴尔泽布，米哈游出品的游戏《原神》及其衍生作品中的角色，又名“雷电影”，“尘世七执政”中的雷神，尊号“雷电将军”，是初代雷神巴尔的妹妹兼影武者。此世最殊胜威怖的雷霆化身，稻妻幕府的最高主宰。挟威权之鸣雷，逐永恒之孤道的寂灭者。
在一次战斗中，“雷电将军”的技能能够召唤出一阵阵的雷和电，导致每次Zbc不得不用他的金钢伞来抵挡。
本题规定，先有雷后有电。“雷电将军”释放技能后，现在空中有n股神秘能量，要么是“雷”，要么是“电“，且保证”雷“在前，”电“在后，且不会出现只有“雷”或只有“电”的情况。
将神秘能量从1到n编号，则存在一个分界点k使得[1,k]全是”雷“，[k+1,n]全是”电“。(1<=k<n)
每一股神秘能量有一个初始能量值ai，如果将这份能量看作”雷 “，则这一股的真实能量为ai×114，如果将这份能量看作”电“，则这一股的真实能量为ai×514。
Zbc的金钢伞的1点防护值可以抵挡1点的能量。
能量和为所有神秘能量的真实能量之和，求Zbc的金钢伞至少需要多少的防护值F(F>=0)才能抵挡“雷电将军”所有的“雷”和“电”的能量和。
在一次战斗中，“雷电将军”的技能能够召唤出一阵阵的雷和电，导致每次Zbc不得不用他的金钢伞来抵挡。
本题规定，先有雷后有电。“雷电将军”释放技能后，现在空中有n股神秘能量，要么是“雷”，要么是“电“，且保证”雷“在前，”电“在后，且不会出现只有“雷”或只有“电”的情况。
将神秘能量从1到n编号，则存在一个分界点k使得[1,k]全是”雷“，[k+1,n]全是”电“。(1<=k<n)
每一股神秘能量有一个初始能量值ai，如果将这份能量看作”雷 “，则这一股的真实能量为ai×114，如果将这份能量看作”电“，则这一股的真实能量为ai×514。
Zbc的金钢伞的1点防护值可以抵挡1点的能量。
能量和为所有神秘能量的真实能量之和，求Zbc的金钢伞至少需要多少的防护值F(F>=0)才能抵挡“雷电将军”所有的“雷”和“电”的能量和。
输入
输入描述：
有多组测试样例。
第一行一个整数t，表示测试样例的数量(1<=t<=10)
第二行一个整数n，表示神秘能量的股数(2<=n<=1e6)
接下来n个整数，表示第i股神秘能量的初始能量值ai(-1e10<=ai<=1e10)
有多组测试样例。
第一行一个整数t，表示测试样例的数量(1<=t<=10)
第二行一个整数n，表示神秘能量的股数(2<=n<=1e6)
接下来n个整数，表示第i股神秘能量的初始能量值ai(-1e10<=ai<=1e10)
输出
输出描述：
对于每一个测试用例，输出一个整数表示Zbc的伞至少需要多少的防护值(F>=0)。
对于每一个测试用例，输出一个整数表示Zbc的伞至少需要多少的防护值(F>=0)。
样例输入 Copy
2
5
2 -9 3 7 5
6
3 3 -5 99 8 7
样例输出 Copy
6912
58710
提示
这题直接可持久化非确定状态AC自动分块维护线段平衡仙人掌优化最小费用最大流预处理混合图上莫比乌斯反演莫队带花舞蹈链并查集树状数组套主席树
预处理动态DP分治FFT求多项式逆元对数函数的指数函数用可持久化并查集合并最小费用循环流上插头DP就ok了，恭喜你AC本题！
于是对于第一个样例，
当k=1时，神秘能量和为114*2+514*(-9+3+7+5)=3312
当k=2时，神秘能量和为114*(2-9)+514*(3+7+5)=6912
当k=3时，神秘能量和为114*(2-9+3)+514*(7+5)=5712
当k=4时，神秘能量和为114*(2-9+3+7)+514*5=2912
综上所述，Zbc需要满足k的所有情况，所以他的金钢伞的最小防护值为6912。
预处理动态DP分治FFT求多项式逆元对数函数的指数函数用可持久化并查集合并最小费用循环流上插头DP就ok了，恭喜你AC本题！
于是对于第一个样例，
当k=1时，神秘能量和为114*2+514*(-9+3+7+5)=3312
当k=2时，神秘能量和为114*(2-9)+514*(3+7+5)=6912
当k=3时，神秘能量和为114*(2-9+3)+514*(7+5)=5712
当k=4时，神秘能量和为114*(2-9+3+7)+514*5=2912
综上所述，Zbc需要满足k的所有情况，所以他的金钢伞的最小防护值为6912。