Given a array of integers and an integer , find a subsequence of this array such that the alternating sum of this subsequence is maximal, and the absolute difference between any two adjacent elements in the subsequence is at most .

If there are multiple solutions, print the lexicographically least.

An array is a subsequence of if can be obtained by deleting some of the elements in . It is not required to delete any elements.

We define the alternating sum of a subsequence as the result of adding each value at an odd index in the sequence (1-indexed), and subtracting each value at an even index in the sequence.

Imagine a sequence of length :

We define the alternating sum of as:

The inequality must hold for

#### Input Specification

The first line will contain integers, .

The second line will contain integers .

#### Output Specification

On the first line, output a single integer, the maximum alternating sum you can obtain.

On the second line, output the indices (1-indexed) of the elements contained in the subsequence.

#### Subtasks

##### Subtask 1 (5%)

##### Subtask 2 (25%)

##### Subtask 3 (70%)

No further constraints.

#### Sample Input 1

```
4 3
-1 2 3 4
```

#### Sample Output 1

```
4
4
```

#### Explanation for Sample 1

The maximum alternating sum is simply , the only element included is at index 4.

#### Sample Input 2

```
5 100
3 -4 -2 -9 10
```

#### Sample Output 2

```
24
1 2 3 4 5
```

#### Explanation for Sample 2

The maximum alternating sum is , which can be obtained by choosing elements ,,, and in your subsequence.

#### Sample Input 3

```
5 7
3 -4 -2 -9 10
```

#### Sample Output 3

```
14
1 2 3 4
```

#### Explanation for Sample 3

The maximum alternating sum is , which can be obtained by choosing elements ,, and in your subsequence. Note that the result here differs from that of sample output two due to the constraint.

## Comments