Trên một con đường, được coi như là một trục số dương xét từ 0 đến ~2^{31}-1,~ có hai công ty ~A~ và ~B~ nhận thi công lắp đặt đèn đường, trong đó ~A~ nhận thi công các đèn phía bên trái con đường còn ~B~ thì lo phía bên phải. Công ty A sẽ lắp đặt đèn đầu tiên ở vị trí a và cách ~d_1~ đơn vị độ dài thì đặt tiếp một cái nữa, và cứ thế lắp tại các vị trí có toạ độ ~a,a+d_1,a+2d_1,…~ Công ty ~B~ tương tự nhưng sẽ lắp đặt đèn đầu tiên ở vị trí ~b~ và cách ~d_2~ đơn vị độ dài thì đặt tiếp một cái nữa, và cứ thế lắp tại các vị trí có toạ độ ~b,b+d_2,b+2d_2,…~ (trong đó ~a,b,d_1,d_2~ đều là các số nguyên dương). Để rèn luyện sức khoẻ, bạn Lan muốn chạy bộ trên con đường này, xuất phát tại một vị trí L nguyên tuỳ ý nào đó thuộc ~[0;10^5]~ và chạy đến vị trí ~L+k~ với ~k~ nguyên. Do chạy vào lúc bình minh, lúc đèn đường không quá sáng nên bạn Lan chỉ thấy rõ cảnh vật hai bên đường ở vị trí x mà tại đó đều có đèn phía bên trái và bên phải. Bạn ấy muốn chọn vị trí xuất phát thích hợp để chạy qua được nhiều nhất những nơi có thể ngắm được cảnh hai bên đường, hãy giúp Lan nhé.

Xác định số lượng nhiều nhất các vị trí mà Lan có thể ngắm cảnh hai bên đường.

Input

Một dòng duy nhất gồm các số nguyên dương ~d_1,a,d_2,b,k~ (theo thứ tự đó) có giá trị không vượt quá ~10^9.~

Output

Một số nguyên duy nhất là số lượng lớn nhất các vị trí mà Lan có thể ngắm cảnh.

Sample input 1

2 1 2 2 2024

Sample output 1

0

Sample input 2

2 1000 4 1000 2024

Sample output 2

507

Sample input 3

2 1 3 1 1000000000

Sample output 3

166666667

Giải thích

Ở test 1, Cty A chỉ lắp đèn tại vị trí lẻ, còn cty B lắp ở vị trí chẵn nên không có vị trí nào mà có đèn của A lẫn B (với mọi cách chọn ~L~).

Ở test 2, Cty A lắp đèn ở vị trí chẵn ~≥1000~ còn cty B lắp đèn ở vị trí chia hết cho ~4~ kể từ ~100~ nên Lan có thể xuất phát từ vị trí ~1000~ là đi qua được ~507~ vị trí chia hết cho ~4~ từ ~1000 \to 3024~.

Ở test 3, Lan có thể xuất phát từ 1 và sẽ đi qua các vị trí chia 6 dư 1, ở đó cả hai bên đều có bóng đèn sáng. Từ 1 đến ~10^9~ sẽ có tất cả ~166666667~ vị trí như thế.

Subtask

• Có 30% số test ứng với 30% số điểm của bài thỏa mãn: ~k≤100.~
• Có 30% số test ứng với 30% số điểm của bài thỏa mãn: ~1≤d_1,d_2≤100.~
• CCó 40% số test ứng với 40% số điểm ứng với giới hạn ban đầu.