Dạy tin học cơ sở luôn là công việc vất vả ngay cả với những giáo viên nhiều kinh nghiệm như thầy HUNGNT. Trong giờ bài tập tin học, có ~n~ học sinh ngồi quanh một bàn tròn, các học sinh được đánh số từ 1 tới ~n~ theo chiều kim đồng hồ. Xuất phát từ một vị trí từ đầu buổi học, thầy HUNGNT phải đi một vòng quanh bàn theo chiều kim đồng hồ để hướng dẫn từng bạn theo đúng thứ tự thầy đi qua. Mỗi bạn được thầy hướng dẫn đúng ~\delta~ micro giây (μs) và sau đó bắt tay vào lập trình ngay trong khi thầy chuyển sang hướng dẫn bạn kế tiếp theo chiều kim đồng hồ..., thời gian di chuyển của thầy coi như không đáng kể.

Do biết rõ kỹ năng lập trình của từng bạn, thầy HUNGNT có thể ước lượng chính xác rằng bạn học sinh thứ ~i~ sau khi được thầy hướng dẫn sẽ cần đúng ~a_i~ μs để viết xong chương trình của mình (~i = 1,2, … , n~). Vấn đề là thầy muốn kết thúc buổi học càng sớm càng tốt, muốn vậy, việc chọn học sinh nào hướng dẫn đầu tiên phải được tính toán kỹ lưỡng.

Yêu cầu: Bạn được cho biết số ~n~, giá trị ~\delta~, dãy ~A = (a_1, a_2, a_3, ..., a_n)~. Hãy giúp thầy HUNGNT chọn vị trí xuất phát sao cho thời gian từ lúc bắt đầu buổi học cho tới khi tất cả các học sinh viết xong chương trình của mình là nhỏ nhất.

Để tránh việc phải đọc một lượng dữ liệu quá lớn, dãy ~A~ sẽ được cho bởi ba số nguyên dương ~p~, ~q~, ~m~ trong đó mỗi phần tử ~a_i~ được xác định theo công thức:

~a_i = (p * i)~ mod ~m~ + ~q~ (~\forall 1 \leq i \leq n~)

Input

• Dòng 1 chứa hai số nguyên dương ~n~, ~\delta~ (~n \leq 5.10^6~; ~\delta \leq 10^9~)
• Dòng 2 chứa ba số nguyên dương ~p~, ~q~, ~m~ xác định dãy ~A~ (~p~, ~q~, ~m~ ~\leq 10^9~)

Output

một số nguyên duy nhất là thời gian (tính bằng μs) từ lúc bắt đầu buổi học cho tới khi tất cả các học sinh viết xong chương trình theo phương án tìm được.

Giới hạn

40% số điểm ứng với các test có ~n \leq 10^3~.

30% số điểm ứng với các test có ~10^4 \leq n \leq 10^5~.

30% số điểm ứng với các test có ~10^6 \leq n \leq 5.10^6~.

Sample Input

5 3
2 1 9

Sample Output

18

Note

Giải thích: ~\delta = 3~; Dãy ~A = (3,5,7,9,2)~.

Phương án tối ưu: Thầy bắt đầu với học sinh ~2~.

Thời điểm viết xong chương trình của từng học sinh như sau:

Học sinh ~2~: ~3 + 5 = 8~

Học sinh ~3~: ~6 + 7 = 13~

Học sinh ~4~: ~9 + 9 = 18~

Học sinh ~5~: ~12 + 2 = 14~

Học sinh ~1~: ~15 + 3 = 18~