T-Shirt Delivery

The New Zealand Algorithm Internet Team Olympiad (KINZA) has ended. After the olympiad the organizers decided to send T-shirts to every prize winner. Delivery of the T-shirts was assigned to the company where the courier Bill works.

Bill has to deliver $n$ T-shirts. He must deliver the parcels in the order in which they appear on his route sheet. If a parcel cannot be delivered, a refusal is marked on the route sheet and Bill drives to the next address.

Bill starts his workday at the company office at time 0. When he arrives at the address of a parcel's recipient, he waits at most $k$ minutes, and if the recipient opens the door within that time, Bill hands over the parcel; the handover itself, not counting the waiting time, takes $t$ minutes. If the door does not open within $k$ minutes and the recipient does not appear, Bill drives on. If the recipient appears exactly $k$ minutes after Bill's arrival, Bill notices it and the parcel is delivered. Bill's workday ends when he finishes handing over the last parcel or marks a refusal to accept it on the route sheet.

Bill's boss John wants to check how diligently Bill works. John knows how long it takes Bill to drive from the office to the first recipient and how long it takes to drive from one recipient to the next. He also conducted a phone survey and knows the time from which each T-shirt recipient will be at home. Now John wants to know when Bill will finish his workday.

The first line of the input file contains three integers $n$, $k$, $t$ ($1 \le n \le 50\,000$, $1 \le k, t \le 10^4$).

The second line contains $n$ natural numbers $z_0, z_1, \ldots, z_{n-1}$, where $z_0$ is the time Bill needs to drive from the office to the first recipient, and $z_i$ is the time Bill needs to travel from the $i$-th recipient to the $(i+1)$-th. All $z_i$ do not exceed $10^4$.

The third line contains $n$ non-negative integers $s_1, s_2, \ldots, s_n$ ($0 \le s_i \le 10^{9}$), where $s_i$ is the time from which the $i$-th recipient is ready to accept the parcel. Bill starts at time 0.

Print a single number: the minimum time in which Bill can complete his task.

In the example Bill arrives at the first recipient at time 1 and hands over the parcel immediately. At time 2 he leaves the first recipient and at time 7 he arrives at the second. He waits 3 minutes, until time 10, but the recipient does not appear, so Bill heads to the third recipient and arrives at time 14. That recipient is at home and accepts the parcel. Bill is therefore free at time 15.