### National Olympiad in Informatics, China, 2010

## Day 1, Problem 2 - Super Piano

Little Z is a minorly famous pianist. Recently, Doctor C has gifted him with a super piano. With it, little Z hopes to create the world's most enchanting music.

The super piano can produce `n` different notes, numbered from 1 to `n`. The **loveliness** of the `i`-th note is `A _{i}`, where

`A`can be positive or negative.

_{i}A "super chord" consists of some number of **numerically consecutive** notes, where the chord does not contain fewer than `L` notes, nor more than `R` notes.

We define the **loveliness** of a chord as the sum of the lovelinesses of all the notes it contains. Two super chords are considered the same if and only if both their sets of notes are identical.

Little Z decides to compose a piece consisting of `k` super chords. To make the piece more extraordinary, little Z requires the piece to also consist of `k` **different** super chords. We define the loveliness of a piece as the sum of the lovelinesses of all its super chords. Little Z would like to know just how lovely the loveliest possible piece can be.

### Input Format

The first line contains four positive integers `n`, `k`, `L`, and `R`. `n` represents the number of notes on the super piano. `k` represents the number of super chords that the piece should consist of. `L` and `R` respectively represent the minimum and maximum number of notes that can be in a single super chord.

### Output Format

The output consists of a single integer, the maximum possible loveliness of a piece that little Z can compose.

### Sample Input

4 3 2 3 3 2 -6 8

### Sample Output

11

### Explanation

There are 5 possible super chords:

- Notes 1 ~ 2, for a total loveliness of 3 + 2 = 5
- Notes 2 ~ 3, for a total loveliness of 2 + (−6) = −4
- Notes 3 ~ 4, for a total loveliness of (−6) + 8 = 2
- Notes 1 ~ 3, for a total loveliness of 3 + 2 + (−6) = −1
- Notes 2 ~ 4, for a total loveliness of 2 + (−6) + 8 = 4

The loveliest composition comprises of super chords 1, 3, and 5 for a total loveliness of 5 + 2 + 4 = 11.

### Constraints

There are 10 total test cases with bounds satisfying:

Test Case | N | k |
---|---|---|

1 | ≤ 10 | ≤ 100 |

2 | ≤ 1,000 | ≤ 500,000 |

3 | ≤ 100,000 | = 1 |

4 | ≤ 10,000 | ≤ 10,000 |

5 | ≤ 500,000 | ≤ 10,000 |

6 | ≤ 80,000 | ≤ 80,000 |

7 | ≤ 100,000 | ≤ 100,000 |

8 | ≤ 100,000 | ≤ 500,000 |

9 | ≤ 500,000 | ≤ 500,000 |

10 | ≤ 500,000 | ≤ 500,000 |

All of the test cases satisfy −1000 ≤ `A _{i}` ≤ 1000 and 1 ≤

`L`≤

`R`≤

`n`. Furthermore, it is guaranteed that a composition fitting the requirements will exist.

All Submissions

Best Solutions

**Point Value:** 25 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 512M

**Added:** Aug 07, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

dutzulon Feb 12, 2015 - 9:32:01 pm UTC