슈퍼 피아노
시간 제한2초메모리 제한512 MB
길이가 L 이상 R 이하인 서로 다른 부분 배열 k개를 골라 원소 합의 총합이 최대가 되도록 한다.
문제
어린 Z는 이름이 조금 알려진 피아니스트이다. 최근 C 박사가 그에게 슈퍼 피아노를 선물했다. Z는 이 피아노로 세상에서 가장 아름다운 음악을 만들고 싶어 한다.
슈퍼 피아노는 n개의 서로 다른 음을 낼 수 있고, 음은 1번부터 n번까지 번호가 붙어 있다. i번 음의 아름다움은 Ai이며, Ai는 양수일 수도 있고 음수일 수도 있다.
"슈퍼 코드"는 번호가 연속한 음 몇 개로 이루어지며, 코드에 포함된 음의 개수는 L개 이상 R개 이하이다.
코드의 아름다움은 코드에 포함된 모든 음의 아름다움의 합으로 정의한다. 두 슈퍼 코드는 포함하는 음의 집합이 완전히 같을 때에만 같은 코드로 본다.
어린 Z는 k개의 슈퍼 코드로 이루어진 곡을 작곡하려고 한다. 곡을 더 특별하게 만들기 위해, Z는 곡이 k개의 서로 다른 슈퍼 코드로 이루어질 것을 요구한다. 곡의 아름다움은 곡에 포함된 모든 슈퍼 코드의 아름다움의 합으로 정의한다. Z는 가장 아름다운 곡이 얼마나 아름다울 수 있는지 알고 싶어 한다.
입력
첫째 줄에 네 양의 정수 n, k, L, R이 주어진다. n은 슈퍼 피아노의 음의 개수, k는 곡을 이루어야 하는 슈퍼 코드의 개수, L과 R은 각각 슈퍼 코드 하나에 포함될 수 있는 음의 개수의 최솟값과 최댓값이다.
출력
어린 Z가 작곡할 수 있는 곡의 아름다움의 최댓값을 하나의 정수로 출력한다.
제한
- 1 ≤ N, k ≤ 500000
- −1000 ≤
Ai≤ 1000 - 1 ≤
L≤R≤n.
조건을 만족하는 곡이 존재함이 보장된다.