Lẩu băng chuyền là một hình thức ăn lẩu trong đó thực khách ngồi quanh một băng chuyền chạy vòng tròn, trên đó có các đĩa nhỏ chứa các loại nguyên liệu tươi sống như thịt, hải sản, rau củ và các loại nấm. Thực khách có thể tùy ý lựa chọn nguyên liệu mà mình muốn và cho vào nồi lẩu đang sôi trước mặt.

Hôm nay, để giải tỏa stress sau buổi ngày ôn luyện căng thẳng, lithium đã đi ăn cho đã đời rồi ôn luyện tiếp. Trên băng chuyền hiện tại có ~n~ đĩa đồ ăn được đặt trên BĂNG CHUYỀN HÌNH TRÒN có độ ngon và giá tiền khác nhau. Anh ấy nghĩ rằng, cái bụng của ảnh chỉ chứa được ~k~ đĩa đồ ăn. Vì là một người có tiền nên anh ấy muốn ăn một cách ngon miệng (anh ấy sẽ tối đa hóa độ ngon rồi mới cực tiểu hóa số tiền). Vì là một người bị OCD nên anh ấy phải chọn ~k~ đĩa đồ ăn liên tiếp. Nhưng vì học quá mệt mỏi nên lithium nhờ bạn tìm cách sao cho giúp anh ấy ăn ngon miệng nhất có thể để anh ấy có sức học tiếp 😋😋😋.

Input

Dòng đứa cho số nguyên dương ~n, k~ tượng trưng cho số đĩa trên băng chuyền và số lượng đĩa anh ấy chọn.

Dòng tiếp theo chứa dãy số ~d_1, d_2, \dots, d_i, \dots, d_n~ tượng trưng cho độ ngon của món ăn ~i~.

Dòng tiếp theo chứa dãy số ~c_1, c_2, \dots, c_i, \dots, c_n~ tượng trưng cho giá tiềncủa món ăn ~i~.

Output

Ghi ra độ ngon lớn nhất và giá tiền ít nhất khi chọn ~k~ đĩa liên tiếp trên băng chuyền HÌNH TRÒN (ưu tiên độ ngon).

Constraints

~k \leq n \leq 10^6~

~-10^6 \leq d_i \leq 10^9~

~1 \leq c_i \leq 10^9~

Sample Input 1

5 2
1 2 5 4 5
1 2 3 4 5

Sample Output 1

9 7

Sample Input 2

5 2
5 2 5 4 5
100 2 3 4 5

Sample Output 2

10 105

Note

Ở Sample Test 1: Chọn đĩa ~3, 4~ là tối ưu.

Ở Sample Test 2: Chọn đĩa ~5, 1~ là tối ưu (vẫn thỏa mãn chọn ~k~ đĩa liên tiếp).