题目描述
现在有长度为 nnn 的数组 aaa,你可以在两种操作中选择一种进行最多一次操作。
请问进行操作后,最大的数组总和是多少?
- 操作1:
- 操作2:
选择一个数 iii (1≤i≤n)(1\leq i\leq n)(1≤i≤n) 使得 ai:=ai×xa_i:=a_i \times xai:=ai×x,xxx 可以是 [1,n][1,n][1,n] 范围内任意正整数。
输入
输入包含两行.
第一行一个正整数 nnn (1≤n≤2×105)(1\leq n\leq 2 \times 10^5)(1≤n≤2×105) 表示数组 aaa 的长度。
第二行 nnn 个正整数 aia_iai (1≤ai≤109)(1\leq a_i \leq10^9)(1≤ai≤109) 表示数组 aaa 的元素。
第一行一个正整数 nnn (1≤n≤2×105)(1\leq n\leq 2 \times 10^5)(1≤n≤2×105) 表示数组 aaa 的长度。
第二行 nnn 个正整数 aia_iai (1≤ai≤109)(1\leq a_i \leq10^9)(1≤ai≤109) 表示数组 aaa 的元素。
输出
输出包含一行一个整数,表示最大的数组总和。
样例输入 Copy
5
5 3 4 1 2
样例输出 Copy
35
提示
选择第一个数 555 , 5∗55 * 55∗5 后使得数组总和最大,25+3+4+1+2=3525+3+4+1+2=3525+3+4+1+2=35。