Trong giới học sinh chuyên, kỳ thi Học sinh giỏi Quốc gia luôn được ví như một cuộc rèn luyện khổ hạnh. Để chạm tay vào những tấm huy chương danh giá, các tuyển thủ phải đánh đổi hàng tháng trời vùi đầu vào phòng đội tuyển. Dù không có bất kỳ một văn bản chính thức nào quy định, nhưng giữa các thầy cô giáo bộ môn và ban giám hiệu luôn tồn tại một "luật ngầm" đầy tinh tế: tạo mọi điều kiện tối đa cho các sĩ tử trong học kỳ đó. Những bài kiểm tra 15 phút, những buổi dò bài đầu giờ hay cả những cột điểm giữa kỳ đều được nhẹ nhàng gác lại hoặc châm chước, nhường trọn quỹ thời gian cho những chuyên đề chuyên sâu và những đêm thức trắng cùng đam mê.

Thế nhưng, ánh hào quang nào rồi cũng đến lúc nhường chỗ cho thực tại. Khi kỳ thi khép lại, cũng là lúc những "chiến thần" đội tuyển phải tháo bảng tên thí sinh để trở về với nhịp sống của một học sinh chính khóa bình thường. Lúc này, họ phải đối mặt với một món nợ khổng lồ: học lại toàn bộ chương trình của các môn học đã bị bỏ lỡ từ lâu. Từ những chuỗi phản ứng Hóa học rắc rối, những mốc sự kiện Lịch sử dài đằng đẵng, cho đến những bài phân tích Văn học phức tạp... tất cả bỗng chốc trở thành một mớ dây leo chờ được gỡ rối.

Nhìn từ bên ngoài, việc phải lấp đầy lỗ hổng kiến thức khổng lồ ấy trong thời gian ngắn nghe chừng là một thử thách vô vọng. Các tuyển thủ thường bị trêu đùa và gắn mác là những kẻ "học lệch", chỉ biết mỗi môn chuyên mà mù tịt những môn còn lại. Nhưng thực tế chứng minh điều ngược lại, với nền tảng tư duy logic sắc bén đã được tôi luyện qua những thử thách hóc búa nhất, việc "lấy lại gốc" đối với họ không hề gian nan như người ta tưởng. Phần vì khả năng tiếp thu và tự học của họ đã đạt đến độ chín, phần vì mục tiêu ban đầu thường rất thực dụng và khiêm tốn: chỉ cần điểm số vừa đủ an toàn, qua mức trung bình là thành công.

Tuy nhiên, mọi thứ sẽ trở thành một câu chuyện hoàn toàn khác nếu những học sinh "học lệch, mất gốc" ấy thực sự bật chế độ nghiêm túc. Một khi họ quyết tâm dồn sự tập trung và khả năng phân tích hệ thống của mình vào các môn học trên lớp, sức bật của họ là không thể cản phá. Những bài tập từng bị coi là rắc rối bỗng chốc được giải quyết bằng một tư duy rành mạch, tối ưu và đi thẳng vào bản chất vấn đề. Lúc bấy giờ, họ không chỉ lấp đầy khoảng trống kiến thức trong nháy mắt, mà đôi khi còn bứt phá mạnh mẽ, vượt mặt cả những học sinh chăm chỉ nhất lớp, khẳng định một chân lý: tư duy nhạy bén chính là vũ khí tối thượng để chinh phục mọi rào cản.

Trong quá trình lấy gốc đầy quyết tâm ấy, cậu học sinh nhận thấy có ~n~ chuyên đề cần phải chinh phục. Mỗi chuyên đề thứ ~i~ mang lại hai loại lợi ích: hiệu quả cố định ~a_i~ và hiệu quả không cố định ~b_i~.

Việc rèn luyện chuyên đề thứ ~i~, trong giây đầu tiên, sẽ giúp cậu bứt phá và tăng sức mạnh lên một lượng đúng bằng ~a_i + b_i~. Sau đó, cứ mỗi giây tiếp theo dành cho chuyên đề này, phần sức mạnh tăng thêm sẽ bị suy giảm đi ~1~ đơn vị do sự bão hòa kiến thức, cho tới khi chạm đáy và chỉ duy trì ở mức hiệu quả cố định.

Ví dụ, một chuyên đề có hiệu quả cố định là ~6~ và hiệu quả không cố định là ~2~, nếu học sinh đó học chuyên đề này trong ~4~ giây, sức mạnh của học sinh đó sẽ tăng thêm ~(6 + 2) + (6 + 1) + (6 + 0) + (6 + 0) = 27~ đơn vị.

Học sinh ấy chỉ có quỹ thời gian vỏn vẹn ~t~ giây để học. Hãy tính sức mạnh lớn nhất mà cậu có thể đạt được.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 2 \times 10^5~) là số chuyên đề.

Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^8~) - hiệu quả cố định của chuyên đề thứ ~i~.

Dòng tiếp theo chứa ~n~ số nguyên dương ~b_1, b_2, ..., b_n~ (~1 \le b_i \le 10^8~) - hiệu quả không cố định của chuyên đề thứ ~i~.

Dòng cuối cùng chứa số nguyên dương ~t~ (~1 \le t \le 10^{10}~) - thời gian học sinh ấy có.

Output

Sức mạnh lớn nhất học sinh đó có thể đạt được.

Sample Input

2
6 4
2 3
5

Sample Output

34