Geekflix

시간 제한3초메모리 제한1024 MB

요약

원형으로 배치된 n개 스트림에서 i번째를 k번째 재생하면 max(a_i-(k-1)b_i, 0) 코인을 받는다. 버튼을 m번 눌러 얻는 최대 코인을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 구현
정답자: 아직 제출이 없습니다

문제

George got COVID-19 in this morning. He must stay at home in the next seven days for quarantine. As a geek, George only watches Geekflix, the video streaming service for geeks, for recreation during his quarantine period. Geekflix provides $n$ video streams numbered from $1$ to $n$ , and Geekflix also gives some geeky coins to the audiences in their quarantine periods. When George watches stream $i$ for the $k$ -th time in his quarantine period, George gets $\max{(a\_i - (k - 1)b\_i , 0)}$ geeky coins.

The Geekflix app arranges the video streams on a circle. For $1 < i ≤ n$ , the previous stream of stream $i$ is stream $i - 1$ . The previous stream of stream $1$ is stream $n$ . For $1 ≤ i < n$ , the next stream of stream $i$ is stream $i + 1$ . The next stream of stream $n$ is stream $1$ . When George opens the Geekflix app on his TV, the Geekflix app points the cursor at stream $1$ .

The remote controller has three buttons: previous, next, and play. When George presses the previous button, the Geekflix app points the cursor to the previous stream. When George presses the next button, the Geekflix app points the cursor to the next stream. When George presses the play button, the Geekflix app plays the stream pointed by the cursor. The cursor points to the same stream after playing.

George may press the buttons $m$ times during his quarantine period, and he wants to get as many geeky coins as possible. What is the maximum number of geeky coins that George can get during his quarantine period?

입력

The first line contains two positive integers $n$ and $m$ . $n$ is the number of video streams, and George may press the buttons $m$ times. The second line contains $n$ positive integers $a\_1, \dots , a\_n$ , and the third line contains $n$ non-negative integers $b\_1, \dots , b\_n$ . These $2n$ integers define the number of geeky coins awarded to George when the Geekflix app plays video streams.

출력

Output the maximum number of geeky coins that George can get during his quarantine period.

제한

$1 ≤ n ≤ 200$
$1 ≤ m ≤ 1000$
$0 ≤ b\_i ≤ a\_i ≤ 5000$ for $1 ≤ i ≤ n$ .

예제2

예제 1
입력
```
3 10
10 10 10
5 3 1
```
예상 출력
```
67
```
예제 2
입력
```
5 10
1 2 3 4 5
0 1 2 3 4
```
예상 출력
```
16
```