Calculate Maximum Quality Score

You must choose a non-empty range and either multiply all of it by impactFactor or divide all of it by that factor, rounding toward 0. After the operation, find the maximum possible sum of a non-empty contiguous subarray.

输入格式

The first line contains n impactFactor (1≤n≤200000, 1≤impactFactor≤10000); the second line contains n ratings (−100000..100000).

输出格式

Output a single integer answer.

样例 1

输入：

5 2
5 -3 -3 2 4

输出：

12

样例 2

输入：

4 1
-2 3 -3 -1

输出：

3

样例 3

输入：

2 2
-5 -3

输出：

-1

样例说明

Example 1: multiplying the last 2 and 4 by 2 turns them into 4 and 8, for a maximum sum of 12. Example 2: a factor of 1 changes nothing, so choosing 3 gives 3. Example 3: −3 divided by 2 rounded toward 0 is −1, which is the maximum quality score obtainable.