Ngày đầu tiên phòng thí nghiệm có ~a~ cá thể vi khuẩn. Mỗi ngày thí nghiệm diễn ra theo đúng thứ tự:

1. Nhân giống: đưa toàn bộ vi khuẩn vào tủ ấm. Mỗi vi khuẩn tạo thêm ~b~ vi khuẩn mới, nên nếu đầu ngày có ~x~ con thì sau nhân giống có ~x \cdot (b+1)~ con.

2. Lấy ra nghiên cứu: lấy ra đúng ~c~ con để thí nghiệm và tiêu hủy.

   • Nếu số vi khuẩn hiện có ít hơn ~c~ thì lấy hết, nghiên cứu kết thúc (sau đó không còn vi khuẩn).
   • Nếu đủ thì còn lại ~x \cdot (b+1) - c~.
3. Đưa về hộp chứa: hộp chỉ giữ tối đa ~d~ con. Nếu còn nhiều hơn thì chỉ giữ lại ~d~, phần thừa bị tiêu hủy. Tức là số cuối ngày là ~\min(d,; x\cdot(b+1)-c)~ (trong trường hợp không bị kết thúc ở bước 2).

Giáo sư cần biết sau ngày thứ ~k~ còn lại bao nhiêu vi khuẩn.

Yêu cầu

Cho ~a, b, c, d, k~, hãy tính số vi khuẩn còn lại sau khi thực hiện quy trình trên đúng ~k~ ngày (hoặc có thể kết thúc sớm nếu có ngày không đủ ~c~ để lấy ra).

Dữ liệu

• Một dòng chứa 5 số nguyên ~a, b, c, d, k~ với:

• ~1 \le a, b \le 1000~

• ~0 \le c \le 1000~
• ~a \le d \le 1000~
• ~1 \le k \le 10^{18}~

Kết quả

Ghi ra một số nguyên — số vi khuẩn còn lại sau ngày thứ ~k~.

Ví dụ

Ví dụ 1

Input

1 3 1 5 2

Output

5

Giải thích

Ví dụ 1

Ban đầu ~x=1~, ~b=3~ nên mỗi ngày sau nhân giống có ~x\cdot 4~ con.

• Ngày 1: sau nhân giống ~4~, lấy ra ~1~ còn ~3~, hộp chứa giữ ~\min(5,3)=3~.
• Ngày 2: đầu ngày ~3~, sau nhân giống ~12~, lấy ra ~1~ còn ~11~, hộp chứa chỉ giữ tối đa ~5~ nên còn ~5~.

Vậy sau ngày thứ ~2~ còn ~5~ vi khuẩn.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le a, b \le 1000~
• ~0 \le c \le 1000~
• ~a \le d \le 1000~
• ~1 \le k \le 10^{18}~