Một công ty có $n$ máy chủ, được đánh số từ $1$ đến $n$. Máy chủ thứ $i$ chạy $a_i$ dịch vụ.
Đôi khi máy chủ có thể bị tắt, vì vậy một máy chủ dự phòng đã được xác định cho mỗi máy chủ. Với máy chủ có số $i$, máy chủ dự phòng là máy chủ có số $p_i$. Nếu với máy chủ thứ $i$ có $p_i = i$, thì đó là máy chủ có độ tin cậy cao và nó không bao giờ bị tắt.
Với hai máy chủ phân biệt $i$ và $j$, số máy chủ dự phòng $p_i$ và $p_j$ của chúng là phân biệt. Vì vậy, $p$ là một hoán vị độ dài $n$, nghĩa là mỗi số từ $1$ đến $n$ xuất hiện đúng một lần trong các giá trị $p_1, \dots, p_n$.
Quá trình tắt máy chủ diễn ra như sau: nếu máy chủ $i$ tắt, tất cả dịch vụ đang chạy trên nó được chuyển đến máy chủ có số $p_i$, và máy chủ $i$ được thay thế bằng một máy chủ mới mà trên đó không có dịch vụ nào đang chạy. Số của máy chủ này và số của máy chủ dự phòng của nó vẫn không thay đổi. Việc chuyển giao dịch vụ và thay thế máy chủ là một quá trình rất nhanh, trong đó không thể xảy ra tắt máy mới.
Công ty dự định tiến hành một bài kiểm tra hiệu suất hệ thống. Để làm điều này, tối đa $k$ máy chủ sẽ bị tắt. Các lần tắt được thực hiện tuần tự, nghĩa là không có hai máy chủ nào bị tắt đồng thời. Xác định số lượng dịch vụ tối đa có thể tập trung trên một máy chủ duy nhất sau khi tắt tối đa $k$ máy chủ.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($1 \leqslant k < n \leqslant 10^5$) — số lượng máy chủ và số lượng máy chủ tối đa có thể bị tắt.
Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($0 \leqslant a_i \leqslant 10^9$) — số lượng dịch vụ đang chạy trên các máy chủ.
Dòng thứ ba chứa $n$ số nguyên $p_1, p_2, \dots, p_n$ ($1 \leqslant p_i \leqslant n$) — số của các máy chủ dự phòng.
Dữ liệu ra
In ra một số nguyên duy nhất — đáp án của bài toán.
Nhiệm vụ con
| Nhiệm vụ con | Điểm | Giới hạn | Các nhiệm vụ con bắt buộc |
|---|---|---|---|
| 1 | 15 | $n \leqslant 1000, k = 1$ | — |
| 2 | 27 | $n \leqslant 1000$ | 1 |
| 3 | 21 | $p_i = i \pmod n + 1$ | — |
| 4 | 37 | — | 1, 2, 3 |
Ví dụ
Dữ liệu vào 1
4 2 6 10 7 9 2 3 4 1
Dữ liệu ra 1
26
Dữ liệu vào 2
3 1 1000000000 993 2010 1 3 2
Dữ liệu ra 2
1000000000
Dữ liệu vào 3
11 5 3 5 12 7 5 9 2 6 0 9 4 2 8 9 6 5 11 3 1 10 7 4
Dữ liệu ra 3
23
Ghi chú
Xem xét thứ tự tắt máy chủ cho phép đạt được đáp án tối đa trong ví dụ đầu tiên.
Nhắc lại cách thức chuyển giao dịch vụ khi máy chủ tắt:
| Máy chủ | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Dự phòng | 2 | 3 | 4 | 1 |
Đầu tiên, máy chủ thứ hai tắt; dịch vụ của nó chuyển sang máy chủ thứ ba, do đó trên máy chủ thứ ba có $10 + 7 = 17$ dịch vụ.
Sau đó, máy chủ thứ ba tắt; dịch vụ của nó chuyển sang máy chủ thứ tư, sau đó trên máy chủ thứ tư có $9 + 17 = 26$ dịch vụ.
Để hiểu rõ hơn, hãy xem bảng dưới đây, ghi lại số lượng dịch vụ trên mỗi máy chủ trong quá trình mô tả ở trên.
| Giai đoạn | $a_1$ | $a_2$ | $a_3$ | $a_4$ |
|---|---|---|---|---|
| Trước lần tắt đầu | 6 | 10 | 7 | 9 |
| Sau khi tắt máy chủ 2 | 6 | 0 | 17 | 9 |
| Sau khi tắt máy chủ 3 | 6 | 0 | 0 | 26 |
Nếu máy chủ thứ ba tắt trước, rồi máy chủ thứ hai tắt sau, quá trình sẽ như sau:
| Giai đoạn | $a_1$ | $a_2$ | $a_3$ | $a_4$ |
|---|---|---|---|---|
| Trước lần tắt đầu | 6 | 10 | 7 | 9 |
| Sau khi tắt máy chủ 3 | 6 | 10 | 0 | 16 |
| Sau khi tắt máy chủ 2 | 6 | 0 | 10 | 16 |
Trong trường hợp này, số dịch vụ tối đa trên một máy chủ là 16, không phải đáp án tối ưu.
Trong ví dụ thứ hai, một trong các phương án khả thi là không có máy chủ nào tắt. Khi đó có $1000000000$ dịch vụ trên máy chủ đầu tiên, đó là đáp án của bài toán. Nếu máy chủ 2 hoặc 3 tắt, số dịch vụ tối đa cũng nằm trên máy chủ đầu tiên.