Ngày xửa ngày xưa, xưa ơi là xưa, xưa lắm lắm lắm rồi, ở một ngôi làng nọ, có một lão nông nghèo vô danh. Lão mồ côi cha mẹ từ nhỏ, vì thế cuộc đời lão đã phải trải qua nhiều sóng gió ngay cả từ lúc mới lọt lòng. Trong khi những đứa trẻ cùng trang lứa được đi học, được ăn no mặc ấm, thì lão phải chăn trâu, cắt cỏ không công cho tên phú hộ giàu và ác nhất trong thôn, chỉ để đổi lấy một chỗ nằm trong chuồng heo nhà hắn hằng đêm. Tuy nhiên, trong suốt 70 năm tồn tại trên chốn phàm trần này, thăng có, trầm có, lên voi có, xuống chó có, lão vẫn luôn giữ được cái cốt cách thanh cao, trong sạch của mình. Lão chưa bao giờ trộm cắp, ăn chặn từ thiện hay gian lận trong chuyện làm ăn. Bởi thế nên dân làng quý lão lắm, quý cái tính cách nhân hậu, quý cái sự cần kiệm, liêm chính của lão. Vì thế, dân làng đã đặt tên cho ông một cái tên nghe rất thân mật, nhưng cũng rất hay và đẹp: ông Liêm.

Thế nhưng bạn đừng tưởng ông Liêm hiền mà dễ ăn hiếp nhé! Bởi lẽ, ông Liêm có một biệt tài, một ngón nghề siêu đẳng mà lão đã tích cóp trong suốt cả cuộc đời lão, và đó là tài chẻ tre. Thật vậy, tuy tuổi đã ngoài bảy mươi, thế nhưng những động tác múa quạ… à nhầm múa rựa của ông Liêm vẫn mạnh mẽ, vẫn dứt khoát như ngày nào, nếu không muốn nói là ở một đẳng cấp hoàn toàn khác. Tuy xương lão nay đã giòn, mắt lão nay đã yếu, thế nhưng mỗi lần cầm cây rựa lên, lão như một con người hoàn toàn khác. Lão lúc ấy sát khí tỏa ra đằng đằng, cả bốn phương trời mây đen như ùn ùn kéo đến. Lão như một vị tướng thiện chiến trong thời Trung Cổ, thế nhưng nếu so về kỹ năng, thì ngay cả những điệu võ của những chiến thần tay to như Lữ Bố, Liêm Sắc, Chương Dương mà đặt cạnh lão cũng như những bước đi chập chững của loài rùa, như mấy đứa trẻ trâu năm, sáu tuổi đánh trận giả Phờ Ri Phai mà thôi. Chỉ một rựa của lão có thể phang chết queo được cả đàn bò mấy nghìn con của ông lý trưởng, một đòn kiếm khí của lão có thể chẻ đôi ngọt lịm cả bầu trời thành hai phần, khiến cho LeKienThanh mỗi lần như vậy là phải đi bắt rận để lột da đi vá lại. Hơn thế nữa, những đòn chém của lão không chỉ mạnh, mà còn nhanh. Trong vòng một cái chớp mắt, lão có thể dễ dàng chém được những đòn kinh thiên động địa như thế hơn MỘT TRĂM LẦN.

Và tất nhiên, nhân tài ắt sẽ có ngày được trọng dụng. Chiều mùa thu hôm đó, các bô lão trong làng tổ chức ra lễ hội chẻ tre. Mỗi thí sinh phải đóng góp 1 chỉ vàng để được vào thi. Thể lệ cuộc thi rất đơn giản, ban tổ chức sẽ bày ra một cây tre trước mặt thí sinh, và thí sinh phải chặt được cây tre thành các đốt. Người chặt được cây tre trong thời gian ngắn nhất, tất nhiên, sẽ là người chiến thắng. Người chiến thắng sẽ được thưởng một số tiền khổng lồ: 69 lượng vàng! Tuy nhiên, nếu trong cả cuộc thi mà không có ai chẻ được tre bằng dụng cụ ban tổ chức đã cung cấp, thì không ai chiến thắng cả. Bạn tưởng như vậy là dễ ăn ư? Nếu bạn nghĩ như thế thì xin chúc mừng, bạn rất sai, quá sai, cực kì sai! Nếu như cuộc đời đã dễ dàng như thế, thì con người đã không đến với nó bằng nước mắt. Bạn tưởng các bô lão cáo già trong làng chịu mất đến 69 lượng vàng ư? Bạn tưởng các bô lão tổ chức một cuộc thi để thua lỗ tiền bạc ư? Không hề. Bạn biết không, thứ nhất, rựa mà ban tổ chức cung cấp là rựa cùn, rựa gỉ. Chúng cùn, chúng gỉ đến mức mà hai thằng tuần đinh to béo nhất làng lấy rựa ra đi chặt quả dừa cả buổi vẫn chưa xong. Thứ hai, cây tre mà ban tổ chức đưa ra thật ra là làm bằng thép nguyên chất, được nung trong điều kiện hoàn hảo trong hơn một năm! Và cứ như vậy, các chấn bé đù đầu óc ngu si, tứ chi phát triển trong thôn hăng hái xin giang hồ cho vay nặng lãi 1 chỉ vàng để được vào thi, và phải chịu thất bại cay đắng. Mọi việc đều đúng theo toan tính của các bô lão…

Thế nhưng, có một lỗ hổng trong kế hoạch thu tiền của các lão: sự tồn tại phi thường của ông Liêm. Thật vậy, ông Liêm, vì hứng thú với kì thi này, đã lấy toàn bộ số tiền mình ki cóp được trong suốt cuộc đời – đúng 1 chỉ vàng đem đi làm lệ phí cuộc thi. Lúc ông Liêm lên đài, ai ai cũng cười nhạo ông, bởi lẽ, họ không biết rằng, ông Liêm đã luyện tập cực khổ cả cuộc đời ông cho khoảnh khắc huy hoàng này. Trong buổi chiều hôm nay, ông Liêm sẽ thể hiện tất cả những gì mình có. Lúc ông Liêm cầm rựa lên là lúc nụ cười của đám đông đã tắt. Bầu không khí lễ hội bỗng dưng ngột ngạt, áp lực khó tả, không phải vì ông Liêm đánh rắm, mà vì cái hồn kiếm của ông Liêm đang tuôn trào ra bên ngoài. Đám đông nhìn ông Liêm mà như bị mê hoặc, bị thao túng tâm lý. Thứ họ đang nhìn thấy, không còn là hình ảnh một ông lão già yếu gầy còm nhom mà họ đã quen thuộc nữa, mà là một vị tướng, một vị tướng dũng mãnh, đang lặng lẽ rút thanh bảo kiếm của mình ra khỏi bao, chuẩn bị cho một trận tử chiến. Ông Liêm phóng về phía trước với một tốc độ bàn thờ, và chỉ trong một nháy mắt, một trụ sắt nguyên chất, được tinh luyện đến mức độ hoàn hảo đã bị ông Liêm xắt lát ngọt lịm như một cọng hành. Các bô lão mắt chữ A, mồm chữ O nhìn ông Liêm NTN cái trụ sắt mà lòng đau như cắt, nhưng biết sao giờ, đành phải buông hết tất cả thôi. Ông Liêm được thưởng 69 lượng vàng, đúng như thể lệ, từ đó mà đổi đời, còn các bô lão sạt nghiệp, nợ nần chồng chất cao thành đống, không cách nào gỡ được.

Các bô lão cay lắm, hận ông Liêm lắm. Vậy nên, ngay ngày hôm sau, khi tiền trao tay còn chưa nóng, các lão đã bắt ông Liêm phải làm một công việc hết sức nặng nhọc: Làm cối xay gió. Thật vậy, có một khu rừng tre chỉ cách làng vỏn vẹn 5000 cây số. Cây tre trong khu rừng ấy có một tính chất rất thú vị: Đốt thứ nhất tính từ mặt đất lên dài ~1~ mét, đốt thứ ~2~ dài ~2~ mét, đốt thứ ~3~ dài ~3~ mét… đốt thứ ~j~ dài ~j~ mét, và khu rừng có ~n~ cây tre như vậy. Các cây tre được đánh số ~1~, ~2~, ..., ~n~. Cây tre thứ ~i~ sẽ có số đốt là ~H_i~. Trong mỗi cây tre, đốt có thứ tự chẵn sẽ có màu hồng, còn đốt có thứ tự lẻ sẽ có màu tím mộng mơ. Bây giờ, việc của ông Liêm sẽ là chặt mỗi cây tre ấy thành từng đốt, và ghép những đốt chẵn thành đường thẳng riêng, những đốt lẻ thành một đường thẳng riêng, để màu sắc được hài hòa, rồi đặt hai ống thẳng vuông góc tạo thành một hình tam giác vuông, rồi lợp lá lên để làm cánh quạt cho cối xay gió. Ta cần chú ý là từ mỗi cây tre chỉ tạo được một và chỉ một cánh quạt, và mỗi cánh quạt được tạo từ một và chỉ một cây tre, bởi lẽ môi trường của rừng tre rất ư là khắc nghiệt, vì thế các cây tre đã tự tiến hóa để tậu cho mình một sức đề kháng rất mạnh, mạnh đến mức mà hai đốt tre từ hai cây khác nhau không thể ghép lại với nhau, nếu không thì ống tre sẽ nổ tung. Tất nhiên, các bô lão rất muốn dìm ông Liêm, vì vậy các lão bắt ông Liêm phải tận dụng hết tất cả số đốt của một cây vào làm cánh quạt. Việc chặt cây tre thành các đốt thì dễ rồi, thế nhưng ông Liêm lại không biết cần chuẩn bị trước bao nhiêu ~m^2~ lá lợp, để có thể lợp hết được các tam giác vuông tạo thành từ các cây tre từ rừng tre ấy, bởi lẽ cây tre có thể có đến ~10^{18}~ đốt, mà ông Liêm từ nhỏ lại không được học hành đàng hoàng, nên không biết cách tính diện tích hình tam giác vuông. Với tư cách là một lập trình viên pzo vip, bạn có thể nào giúp ông Liêm tính toán ra được cần sử dụng tổng cộng ít nhất là bao nhiêu mét vuông lá lợp để có thể lợp được tất cả các tam giác vuông được không? (cứu thầy Liêm, thầy đang bị deadline dí T.T)

Input:

• Chỉ một dòng, chứa số nguyên dương ~n, a, b, c, M (N \leq 10^{6}; a < M; a, b, c, M \leq 10^{18})~, với ~n~ là số cây tre trong khu rừng. Để tránh phải đọc file dữ liệu quá lớn, bạn sẽ dùng bốn số ~a, b, c, M~ để sinh dãy ~H_i~. Công thức như sau:

Output:

• Là câu trả lời cho bài toán trên. Vì số có thể hơi lớn, nên các bạn hãy in ra luôn, không ~mod~ gì cả.

Ví dụ 1:

Input:

3 1 2 3 69420

Output:

1056

Giải thích test mẫu: Với ~n = 3, a = 1, b = 2, c = 3, M = 69420~, ta sinh ra được dãy độ cao các cây ~H_i~ là ~1, 5, 13~. Từ cây tre 1, ta có thể ghép được một cánh quạt có hình tam giác vuông có chiều dài hai cạnh là ~(1, 0)~, do đó diện tích là ~0~. Tương tự, cây thứ 2 sẽ cho ra cánh quạt hình tam giác vuông, có chiều dài hai cạnh là ~(6, 9)~, diện tích là ~27~, cây thứ 3 sẽ cho ra cánh quạt hình tam giác vuông có chiều dài hai cạnh là ~(42, 49)~, diện tích là ~1029~. Do đó, để lợp hết ba cánh quạt, ta cần ít nhất ~1056~ ~m^2~ lá.

• Subtask 1: (35% số điểm): Đảm bảo dữ liệu đầu ra không vượt quá ~8 * 10 ^ {18}~.
• Subtask 2: (15% số điểm): ~N \leq 30000~.
• Subtask 3: (50% số điểm): ~N \leq 1770130~.