頁面無法載入？點擊這裡可能會修復。
Placeholder

#8519
子任務

기린 1s 32MB

問題

여러분은 가장 강력한 동물이 무엇이라고 생각하는가?

아마도 참새를 떠올릴 것 같다.

하지만 "기린" 이 더 강력할지도 모른다.

기린은 무려 긴 목으로 나무 위의 열매를 먹을 수 있기 때문이다.

사과나무 2N그루가 N그루씩 왼쪽, 오른쪽의 두 줄로 놓여있다.

왼쪽의 N그루에는 각각 L_1, L_2, \cdots, L_N개의 사과가 열려있다.

오른쪽의 N그루에는 각각 R_1, R_2, \cdots, R_N개의 사과가 열려있다.

기린은 오른쪽 첫 번째 나무에 서있다.

기린은 한 시간마다 나무에 있는 모든 사과를 뜯어먹고 인접한 다른 나무로 이동한다.

즉, 같은 줄에서 이전 또는 다음 나무로 이동하거나, 같은 위치의 반대 줄로 이동한다.

한 번 뜯어먹은 사과는 다시 자라나지 않는다.

K시간 뒤에 기린이 먹을 수 있는 사과의 최대 개수를 구해보자.


輸入

첫 줄에 N (1 \le N \le 15)과 K (1 \le K \le 15)가 주어진다.

둘째 줄에 L_1, L_2, \cdots, L_N가 주어진다. (0 \le L_i \le 1000)

셋째 줄에 R_1, R_2, \cdots, R_N가 주어진다. (0 \le R_i \le 1000)


輸出

K시간 뒤에 기린이 먹을 수 있는 사과의 최대 개수를 출력하라.


子任務

編號 分數 條件
#140分

모든 나무에 열려 있는 사과의 개수가 동일하다.

#260分

추가적인 제약 조건이 없다.


範例 #1

2 2
7 3
6 4
13

範例 #2

5 7
30 20 10 30 20
20 0 1 3 40
170

範例 #3

4 4
10 10 10 10
10 10 10 10
40

範例 #4

5 8
20 20 20 10 20
20 10 20 20 20
160


來源

Swedish Olympiad in Informatics 2015 예선

需要登入才能撰寫程式碼。