Khủng bố tại ParkView

Nữ đặc vụ Lexis vừa được tổ chức C9 cử đến khách sạn ParkView để tiêu diệt các phần tử khủng bố đang ẩn náu tại đây.

Khách sạn ParkView gồm n phòng được đánh số từ 1 đến n, phòng thứ i có một tên khủng bố với sức mạnh là $a_{i}$. Để vào được phòng i, Lexis buộc phải đi qua cửa phòng và chịu sự tấn công của quả bom do tên khủng bố gài từ trước, làm giảm sức mạnh của cô đi một lượng bằng $b_{i}$.

Tại phòng thứ i, Lexis có thể tiêu diệt tên khủng bố nếu sức mạnh hiện tại của cô lớn hơn sức mạnh của hắn và nhận phần thưởng là $c_{i}$ đồng, đồng thời tìm được một mật đạo đi đến phòng $i+1$ (phòng n sẽ không có mật đạo) mà không cần mở cửa (và không bị bom tấn công). Ngoài ra, vì ngân sách của tổ chức có hạn, nếu sau khi hoàn thành nhiệm vụ, tổng số tiền thưởng Lexis nhận được vượt quá k đồng, cô sẽ phải rời khỏi ParkView và không nhận được bất kỳ đồng tiền thưởng nào.

Tuy nhiên, Lexis không biết rằng ở một số căn phòng có đồng minh ngầm trà trộn vào, nên khi vô tình hạ gục họ, phần thưởng cô nhận được sẽ là số âm (nghĩa là cô bị phạt tiền). Lưu ý rằng việc tiêu diệt nhầm đồng minh không ảnh hưởng đến khả năng tiếp tục nhiệm vụ của Lexis.

Vì khá kiêu ngạo, Lexis sẽ chỉ mở cửa đúng một lần tại ParkView và có thể kết thúc nhiệm vụ bất cứ khi nào cô muốn.

Cho biết sức mạnh ban đầu của Lexis là P, hãy tính số tiền thưởng lớn nhất mà Lexis có thể nhận được.

Đầu vào:

• Dòng đầu tiên chứa 3 số nguyên n, P, k.
• Dòng thứ hai chứa n số nguyên $a_{1}, a_{2}, ..., a_{n}$ cách nhau bởi khoảng trắng.
• Dòng thứ ba chứa n số nguyên $b_{1}, b_{2}, ..., b_{n}$ cách nhau bởi khoảng trắng.
• Dòng cuối cùng chứa n số nguyên $c_{1}, c_{2}, ..., c_{n}$ cách nhau bởi khoảng trắng.

Đầu ra:

• Một số nguyên duy nhất là số tiền thưởng lớn nhất mà Lexis có thể nhận được.

Giới hạn:

• $1\le n \le 10^{5}$
• $1\le k \le 10^{18}$
• $1\le a_{i} \le 10^{9}$ $(\forall 1 \le i \le n$)
• $1\le b_{i} < P \le 10^{9}$ $(\forall 1 \le i \le n$)
• $-10^{9}\le c_{i} \le 10^{9}$ $(\forall 1 \le i \le n$)

Subtask (tham khảo):

• Subtask 1 (30% số test): $n\le5000$
• Subtask 2 (70% số test): không có giới hạn gì thêm.

Giải thích: Lexis mở cửa phòng thứ nhất, cô bị bom tấn công và sức mạnh còn lại của cô là 5 - 2 = 3. Vì 3 > 2, cô tiêu diệt tên khủng bố ở phòng thứ nhất và nhận 2 đồng, đồng thời tìm được mật đạo sang phòng thứ hai. Vì 3 > 1, cô tiếp tục tiêu diệt tên khủng bố ở phòng thứ hai và nhận 7 đồng. Sau đó Lexis chọn rời khỏi ParkView với 9 đồng tiền thưởng. Có thể chứng minh được không có cách nào khác giúp Lexis kiếm được nhiều hơn 9 đồng tiền (mà không vượt quá ngân sách của tổ chức là 10 đồng).

Ví dụ 1:

Đầu vào:

3 5 10
2 1 3
2 4 1
2 7 6

Đầu ra:

9