Megumin loves magical explosions. Since you are Megumin's most trusted adviser, you want to help her to create the most spectacular explosion ever.
Megumin currently has
Each component
- Controlled combination: the two components will combine together to make a new component with potency
. - Unstable combination: the two components will combine together to make a new component with potency
.
After Megumin applies operations
Input Specification
The first line of input will contain the integer
The second line of input will contain
Output Specification
The first line of output should contain the smallest explosion Megumin can make.
The second line of output should contain the largest explosion Megumin can make.
Constraints
For all subtasks:
Subtask 1 [20%]
Subtask 2 [35%]
At most
Subtask 3 [45%]
No additional constraints.
Sample Input
3
2 1 3
Sample Output
5
9
Explanation of Output for Sample Input
To make the smallest explosion, first Megumin should combine the components with potencies 2 and 3 with a controlled combination and then combine the remaining components with unstable combinations.
To make the largest explosion, first Megumin should combine the components with potencies 1 and 2 with a controlled combination and then combine the remaining components with unstable combinations.
Comments
Prevent stack overflow?
How can I prevent my submission from overflowing due to the excessively large integers resulting from multiplying the list?
Taking the modulus of a number after multiplication and addition won't affect the answer. (I'm guessing you meant number overflow rather than stack overflow)
Thank you my friend. Thank you.
pls help me I don't know why my submission is wrong?
I would look into what happens when you combine components of size 2 and 1 and how it compares to what happens when you just add 1 to the lowest component.