Thầy Luna là một người rất bộn rộn trong suốt cả năm học. Một mùa thi ICPC ở Huế lại sắp đến, thầy phải ngồi soạn đề để cho mấy em học sinh của mình cày code nên thầy ngày càng bận rộn hơn. Hiện tại còn N ngày nữa là đến kỳ thi ICPC ở Huế. Thầy sẽ ra K vấn đề cho các em học sinh của mình. Thầy sẽ ngồi suy nghĩ vấn đề mới - mất ~X_i~ đơn vị thời gian, sinh testcase và viết solution - mất ~Y_i~ đơn vị thời gian. Tất nhiên là thầy sẽ suy nghĩ vấn đề trước khi sinh testcase và viết solution. Tuy nhiên sắp tới 20/11 nên thầy muốn hoàn thành bộ đề càng sớm càng tốt đề có thời gian nghỉ ngơi sau chuỗi ngày chăm chỉ.

Thầy Luna có khả năng dự đoán tương lai, đã tính được thời gian mình sẽ nghỉ ngơi. Bây giờ thầy đang đố bạn tính được thời gian ít nhất đề hoàn thành k vấn đề.

Input

Dòng đầu tiên gồm 2 số n và k (~ 1 \le k \le n \le 2011 ~).

Dòng thứ hai gồm N số ~X_1, X_2, ..., X_n~ (~1 \le X_i \le 10^9~) - thời gian để suy nghĩ vấn đề vào ngày thứ i.

Dòng thứ hai gồm N số ~Y_1, Y_2, ..., Y_n~ (~1 \le Y_i \le 10^9~) - thời gian để sinh testcase và viết solution vào ngày thứ i.

Output

Một dòng duy nhất là thời gian ít nhất thầy Luna đề hoàn thành k vấn đề. Hay giá trị nhỏ nhất của ~X_{i1} + X_{i2} + ... + X_{ik} + Y_{j1} + Y_{j2} + ... + Y_{jk}~ thỏa ~1 \le i_1 < i_2 < ... < i_k \le n~ , ~1 \le j_1 < j_2 < ... < j_k \le n~ và ~i_1 \le j_1, i_2 \le j_2, ... , i_k \le j_k~

Subtask 1: 30% số điểm (~1 \le n \le 10 ~)

Subtask 2: 70% số điểm (không có ràng buộc gì thêm)

Examples

Input

6 3
2 9 11 7 15 6 
4 8 3 13 5 15  

Output

30 

Giải thích: Thầy Luna sẽ suy nghĩ vấn đề thứ nhất vào ngày 1 (mất 2 đơn vị thời gian) - sinh testcase và viết solution vào ngày 1 (mất 4 đơn vị thời gian). Suy nghĩ vấn đề thứ hai vào ngày 2 (mất 9 đơn vị thời gian) - sinh testcase và viết solution vào ngày 3 (mất 3 đơn vị thời gian). Suy nghĩ vấn đề thứ ba vào ngày 4 (mất 7 đơn vị thời gian) - sinh testcase và viết solution vào ngày 5 (mất 5 đơn vị thời gian). Tổng cộng thầy mất 2 + 4 + 9 + 3 + 7 + 5 = 30 đơn vị thời gian

Input

5 1
6 8 7 12 15 
7 5 4 8 11 

Output

10