책

마르코는 Interliber 도서전에 가서 책 $n$권을 샀다. $i$번째 책의 매력도는 $k_i$이다. 마르코는 매력도 순서대로 책을 선반에 꽂았다. 왼쪽 끝 책이 가장 매력이 낮고, 오른쪽으로 갈수록 바로 앞 책과 같거나 더 매력적이다.

Interliber 도서전 이후 꽤 시간이 지났지만, 마르코는 이제서야 책을 읽을 시간이 생겼다. 그는 독서에 총 $t$분을 쓴다.

각 책에 대해 마르코는 책 전체를 읽거나, 표지의 내용만 읽을 수 있다. 전체를 읽으면 $a$분이 걸리고, 표지만 읽으면 $b$분이 걸린다.

마르코는 가장 왼쪽 책부터 읽기 시작한다. 현재 책을 다 읽으면(전체를 읽었든 표지만 읽었든) 방금 읽은 책의 바로 오른쪽 책으로 넘어간다. 마르코의 영감은 전체를 읽은 책들의 매력도 합이다. $t$분이 지난 뒤 얻을 수 있는 영감의 최댓값은 얼마인가?

참고: 마르코가 책을 읽기 시작했지만 $t$분이 끝나기 전에 다 읽지 못하면, 그 책은 영감에 기여하지 않는다.

첫째 줄에 정수 $n$, $t$, $a$, $b$가 주어진다 ($1 \le n \le 2 \cdot 10^5$, $1 \le t \le 10^9$, $1 \le b < a \le 10^9$). 차례대로 책의 수, 마르코가 독서에 쓰는 시간, 책 전체를 읽는 데 걸리는 시간, 표지의 내용만 읽는 데 걸리는 시간이다.

둘째 줄에 책의 매력도 $k_i$ ($1 \le k_i \le 10^9$, $k_i \le k_{i+1}$) $n$개가 주어진다.

$t$분 뒤 마르코가 얻을 수 있는 영감의 최댓값을 첫째 줄에 출력한다.