Bờm có ~a~ khối hình hộp màu đỏ và ~b~ khối hình hộp màu xanh. Các khối màu đỏ có chiều cao ~x~, các khối màu xanh có chiều cao ~y~.

Bờm muốn chọn một số khối hộp và xếp chúng chồng lên nhau thành một tháp sao cho không có hai hộp liền kề nào cùng màu.

Yêu cầu

Hãy viết chương trình xác định số độ cao mà Bờm có thể xếp được.

Dữ liệu đầu vào

Gồm bốn số nguyên ~x,\ y,\ a,\ b~ ~(1 \le x, y, a, b \le 10^9)~.

Dữ liệu đầu ra

Gồm một số nguyên là số độ cao của tháp Bờm có thể xếp được.

Ví dụ

Ví dụ 1

INPUT

1 2 3 3

OUTPUT

9

Giải thích:

Cho dãy gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~.

Với số nguyên không âm ~m~, ta định nghĩa ~f(m) = (m \mod a_1) + (m \mod a_2) + ... + (m \mod a_N)~. Trong đó, ~(m \mod a_i)~ là kết quả của phép chia lấy dư của ~m~ cho ~a_i~ ~(\forall i = 1...N)~.

Yêu cầu

Viết chương trình trình tìm giá trị lớn nhất có thể của hàm ~f~.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng 1: ghi số nguyên ~N~ ~(2 \le N \le 3000)~;
• Dòng 2: ghi ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(2 \le a_i \le 10^5)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là giá trị lớn nhất có thể của ~f~.

Ví dụ

Ví dụ 1

INPUT

3
3 4 6

OUTPUT

10

Giải thích: Chọn ~m = 11~: ~f(11) = (11 \mod 3) + (11 \mod 4) + (11 \mod 6) = 10~. Đây là giá trị lớn nhất có thể của ~f~.

Quốc gia X gồm ~N~ hòn đảo (đánh số từ ~1~ đến ~N~) xếp thành một hàng dài từ trái sang phải. Những hòn đảo này được nối với nhau bởi các cây cầu. Cây cầu thứ ~i~ nối hòn đảo thứ ~i~ với hòn đảo thứ ~i + 1~.

Một ngày nọ, giữa một số cặp hòn đảo đã xảy ra tranh chấp, nhà vua quyết định dỡ bỏ một số cây cầu để không có cách nào di chuyển giữa các hòn đảo xung đột nữa. Có nhiều cách để dỡ cầu thoả mãn điều kiện trên, nhưng nhà vua cần bạn giúp ông ấy tìm ra cách dỡ bỏ ít cây cầu nhất nhằm mục đích tiết kiệm chi phí.

Yêu cầu

Viết chương trình tìm số cây cầu ít nhất cần dỡ bỏ theo yêu cầu của nhà vua.

Dữ liệu đầu vào

Gồm ~M + 1~ dòng:

• Dòng 1: gồm hai số nguyên ~N,\ M~ ~(2 \le N \le 10^5;\ 1 \le M \le 10^5)~ ứng với số hòn đảo của quốc gia X và số cặp hòn đảo xảy ra xung đột;
• Tiếp theo là ~M~ dòng, mỗi dòng gồm hai số nguyên ~a_i,\ b_i~ ~(1 \le a_i, b_i \le N;\ a_i \ne b_i)~ mô tả một cặp hòn đảo xảy ra xung đột. Tất cả các cặp ~(a_i, b_i)~ này đôi một phân biệt.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số cây cầu ít nhất cần dỡ bỏ theo yêu cầu của nhà vua.

Ví dụ

Ví dụ 1

INPUT

5 2
1 4
2 5

OUTPUT

1

Giải thích: Chỉ cần loại bỏ cây cầu nối giữa cặp hòn đảo ~(2, 3)~.

Bờm muốn mua một bó hoa gồm ~n~ bông hoa để tặng bạn nhân ngày Quốc tế Phụ nữ. Tại cửa hàng hoa, Bờm phát hiện được:

• Cửa hàng có ~m~ loại hoa, đánh số ~1..m~, mỗi loại hoa đều có ít nhất ~n~ bông;
• Với loại hoa ~i~, bông đầu tiên có trong bó hoa sẽ cung cấp điểm thẩm mĩ ~a_i~, mỗi bông tiếp theo cung cấp điểm thẩm mĩ ~b_i~, nghĩa là nếu Bờm mua ~x_i~ ~(x_i > 0)~ bông hoa loại ~i~, điểm thẩm mĩ loại hoa này đóng góp cho bó hoa sẽ là ~a_i + (x_i - 1) \times b_i~.

Yêu cầu

Hãy viết chương trình xác định tổng điểm thẩm mĩ lớn nhất của bó hoa Bờm có thể mua được.

Dữ liệu đầu vào

Gồm ~m + 1~ dòng:

• Dòng 1: hai số nguyên ~n,\ m~ ~(1 \le n \le 10^9;\ 1 \le m \le 10^5)~;
• Dòng ~2..m + 1~: dòng ~i + 1~ ghi hai số nguyên ~a_i,\ b_i~ ~(0 \le a_i, b_i \le 10^9)~.

Dữ liệu đầu ra

Gồm số nguyên là điểm thẩm mĩ lớn nhất một bó hoa gồm ~n~ bông hoa có thể đạt được.

Ràng buộc dữ liệu

• 8% điểm: ~n, m \le 7~ và ~a_i \ge b_i\ \forall\ i = 1..m~;
• 12% điểm khác: ~n, m \le 7~;
• 12% điểm khác: ~n, m \le 1000~ và ~a_i \ge b_i\ \forall\ i = 1..m~;
• 28% điểm khác: ~n, m \le 1000~;
• 32% điểm khác: ~a_i \ge b_i\ \forall\ i = 1..m~;
• 8% điểm còn lại: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

INPUT

4 3
5 0
1 4
2 2

OUTPUT

14

Giải thích: Bó hoa tối ưu gồm ~1~ bông hoa loại ~1~ và ~3~ bông hoa loại ~2~. Tổng điểm: ~5 + 1 + 4 + 4 = 14~.

Ví dụ 2

INPUT

5 3
5 2
4 2
3 1

OUTPUT

16

Giải thích: Bó hoa tối ưu gồm ~2~ bông hoa loại ~1~ và ~2~ bông hoa loại ~2~ và ~1~ bông hoa loại ~3~. Tổng điểm: ~5 + 2 + 4 + 2 + 3 = 16~.