1. You are given an array(arr1) of integers and an integer k.
2. Another array(arr2) is formed by concatenating K copies of arr1.
For example, if arr1 = {1,2} and k = 3, then arr2 = {1,2,1,2,1,2}.
3. You have to find the maximum subarray sum in arr2.Input Format
A number N a1 a2.. N integers A number K
Output Format
A number representing maximum sum subarray in arr2.
Constraints
1 <= N <= 10^5 1 <= K <= 10^5 -10^6 <= arr1[i] <= 10^6
Example
Input
3 1 2 3 3
Output
18