题目背景

@Luckyer 是一个科学爱好者，每天都在实验室里研究他的电磁装置，但这天他的装置出了点小问题。

题目描述

@Luckyer 有 $n$ 个装置和两个电源，且这些装置是串联的。换句话说，这些装置是一个形似链表的链接方式，除了第 $n$ 个装置，第 $i$ 个装置与第 $i + 1$ 个装置有一条链相连，也就是无头单向非循环链表。

那么这些装置是如何运行的呢？它们只能相邻的 $l$ 个装置共同运行，其中 $l \in \left[ L，R \right]$，只要将两个电源在它们的首尾处与其串联即可。简而言之，将相邻的 $l$ 个装置看作是一个链表，分别将两个电源进行头插和尾插，即可使用这 $l$ 个装置。

但一起运行会造成能量不稳定，聪明的 @Luckyer 想到设定一个稳定值 $k$ ，有利于装置的运行，$k$ 是这么确定的：

• 假定你知道 $n$ 个装置各自的能量值，第 $i$ 个装置的能量值为 $a_i$。当你一起使用多个装置时，它们的总能量值等于每个装置能量值相加。给定你一个可取方案数 $m$，在插入首尾电源的情况下，有至少 $m$ 个电源位置不同的方案使得它们的能量值大于或等于 $k$，就说明这个 $k$ 是合法的，且 $k$ 必须为正整数。

请你快速求出所有合法 $k$ 中的最大值，如不存在，请输出一个数 $-1$。

输入格式

第一行输入四个整数 $n$，$m$，$L$，$R$。

第二行输入 $n$ 个数，第 $i$ 个数表示第 $i$ 个装置的能量值 $a_i$。

输出格式

输出一个整数，即可设置最大的稳定值 $k$ ,若不存在，输出 $-1$。

5 2 2 3
1 3 2 4 5

9

数据规模与约定

对于 $30 \%$ 的数据满足 $1$ $\le$ $L$ $\le$ $R$ $\le$ $n$ $\le$ $1000$。

对于 $100 \%$ 的数据满足 $1$ $\le$ $L$ $\le$ $R$ $\le$ $n$ $\le$ $3\times10^6$ ，$1$ $\le$ $a_i$ $\le$ $10^9$ ，$1$ $\le$ $m$ $\le$ $10^9$。