Sản xuất tuần tự (Sequential Manufacturing)

Nguồn: Kattis

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một dây chuyền gồm $n$ công đoạn sản xuất. Mỗi sản phẩm phải lần lượt đi qua toàn bộ các công đoạn. Công đoạn thứ $i$ cần $t_i$ đơn vị thời gian để xử lý một sản phẩm, và tại một thời điểm mỗi công đoạn chỉ xử lý được một sản phẩm.

Cần hoàn tất $p$ sản phẩm giống nhau. Các sản phẩm được đưa vào dây chuyền sớm nhất có thể nhưng không được gây xung đột xử lý ở bất kỳ công đoạn nào.

Hãy tính thời điểm sớm nhất mà cả $p$ sản phẩm đều hoàn tất.

Input

Dòng đầu chứa hai số nguyên $n,p$.

Dòng thứ hai chứa $n$ số nguyên $t_1,t_2,\ldots,t_n$, là thời gian xử lý tại các vị trí liên tiếp trên dây chuyền.

Dòng thứ ba chứa đúng $n$ số nguyên phụ trợ $k_1,k_2,\ldots,k_n$, được giữ lại để tương thích với định dạng đầu vào của bài nguồn. Trong bộ dữ liệu Phước Hưng OJ Extended, mỗi $k_i$ thỏa $1\le k_i\le n$; các giá trị này không làm thay đổi thời gian xử lý của các công đoạn, vốn được xác định bởi dãy $t_i$ ở dòng thứ hai.

Output

In thời gian nhỏ nhất để hoàn tất toàn bộ $p$ sản phẩm.

Subtask

• Subtask 1 (20%): $1\le n\le 20$, $1\le p\le 100$, $1\le t_i\le 1000$, $1\le k_i\le n$.
• Subtask 2 (30%): $1\le n\le 5000$, $1\le p\le 1000000$, $1\le t_i\le 1000000$, $1\le k_i\le n$.
• Subtask 3 (50%): $1\le n\le 200000$, $1\le p\le 1000000000$, $1\le t_i\le 1000000000$, $1\le k_i\le n$.

Ví dụ

Input

3 2
2 5 3
1 2 3

Output

15

Giải thích

Sản phẩm đầu tiên phải đi qua cả ba công đoạn nên cần

đơn vị thời gian để hoàn tất. Công đoạn thứ hai mất $5$ đơn vị cho mỗi sản phẩm và là công đoạn lâu nhất, nên hai sản phẩm liên tiếp không thể đi qua dây chuyền với khoảng cách hoàn tất nhỏ hơn $5$ đơn vị thời gian.

Có thể đưa sản phẩm thứ hai vào dây chuyền sao cho khoảng cách này đúng bằng $5$. Do đó sản phẩm thứ hai hoàn tất tại thời điểm $10+5=15$, là kết quả cần in. Dòng phụ trợ 1 2 3 chỉ thuộc định dạng input và không thay đổi thời gian xử lý trong ví dụ.