Huy là một học sinh yêu thích cờ vua, toán học và lập trình. Huy biết rằng quân cờ mạnh nhất trên bàn cờ vua là quân Hậu, vì nó có thể di chuyển như quân Xe (trên cùng một cột hoặc một hàng) và như quân Tượng (theo đường chèo).

Yêu cầu

Huy có một bàn cờ hình chữ nhật kích thước ~N \times M~. Huy muốn biết nếu đặt một quân Hậu lên bàn cờ này thi số lượng ô tối đa mà nó có thể kiểm soát là bao nhiêu. Chẳng hạn, nếu ~N = M = 8~ thì một quân Hậu có thể kiểm soát tối đa ~27~ ô (không tính ô đặt quân Hậu, xem giải thích test ví dụ ~1~).

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng 1: số nguyên ~N~ ~(1 \le N \le 10^9)~ là kích thước bàn cờ theo chiều dọc.
• Dòng 2: số nguyên ~M~ ~(1 \le M \le 10^9)~ là kích thước bàn cờ theo chiều ngang.

Dữ liệu đầu ra

Gồm một số nguyên là số lượng ô tối đa mà quân Hậu có thể kiểm soát trên bàn cờ kích thước ~N \times M~.

Ràng buộc dữ liệu

• 42% điểm dành cho các test có ~N, M \le 10~.
• 38% điểm khác dành cho các test có ~N, M \le 500~.
• 20% điểm còn lại không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

INPUT

8
8

OUTPUT

27

Giải thích:

Ví dụ 2

INPUT

3
4

OUTPUT

9

Giải thích:

Trung vị của một dãy số ~X = (x_{1}, x_{2}, ..., x_N)~ được xác định như sau:

• Xét dãy ~Y = (y_{1}, y_{2}, ..., y_N)~ là kết quả của việc sắp xếp dãy ~X~ theo thứ tự không giảm;
• Nếu ~N = 2k~ trung vị dãy ~X~ là ~y_k~, nếu ~N = 2k + 1~, trung vị của dãy ~X~ là ~y_{k + 1}~.

Chẳng hạn, trung vị của dãy ~X = (3, 1, 2, 4)~ là ~2~, trung vị của dãy ~X = (1, 3, 2, 3, 5)~ là ~3~.

Huy có một dãy số ~A = (a_{1}, a_{2}, ..., a_N)~. Huy muốn biến đổi dãy số về dạng dãy hằng (dãy có tất cả các phần tử bằng nhau) bằng cách sử dụng số lần phép biến đổi:

• Chọn hai chỉ số ~l~ và ~r~ ~(1 \le l < r \le N)~, gọi ~x~ là trung vị của đoạn con ~(a_l, a_{l + 1}, ..., a_r)~;
• Gán tất cả các phần tử ~a_l, a_{l + 1}, ..., a_r~ thành ~x~.

Chẳng hạn, nếu ~A = (1, 3, 5, 2, 4)~, thực hiện biến đổi trên với ~l = 3~ và ~r = 4~ thì dãy trở thành ~A = (1, 3, 2, 2, 4)~.

Yêu cầu

Hãy giúp Huy xác định giá trị lớn nhất của phần tử dãy hằng có thể nhận được từ dãy ~A~.

Dữ liệu đầu vào

Gồm hai dòng:

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

Dữ liệu đầu ra

Gồm một số nguyên kết quả.

Ràng buộc dữ liệu

• 30% điểm dành cho các test có ~2 \le N \le 10^2;\ 1 \le a_{i} \le 10^5\ \forall\ i~;
• 30% điểm khác dành cho các test có ~10^2 \le N \le 10^3;\ 10^5 \le a_{i} \le 10^6\ \forall\ i~;
• 40% điểm còn lại không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

INPUT

5
1 2 3 4 5

OUTPUT

4

Giải thích: Có thể thực hiện ~3~ phép biến đổi sau:

• ~(l, r) = (4, 5)~ thì dãy mới ~A = [1, 2, 3, 4, 4]~
• ~(l, r) = (3, 5)~ thì dãy mới ~A = [1, 2, 4, 4, 4]~
• ~(l, r) = (1, 5)~ thì dãy mới ~A = [4, 4, 4, 4, 4]~

Một xâu ~A~ được gọi là rút gọn của xâu ~B~ nếu ta có thể tạo ra ~A~ bằng cách xóa đi ~0~ hoặc nhiều ký tự trong ~B~ mà không thay đổi thứ tự các ký tự còn lại. Theo định nghĩa này, một xâu luôn là xâu rút gọn của chính nó.

Chẳng hạn:

• ac, ab, aa là các xâu rút gọn của aabc;
• d, aaa, ba không phải là xâu rút gọn của aabc.

Yêu cầu

Cho hai xâu ~S~ và ~T~ chỉ gồm các ký tự chữ cái thường trong bảng chữ cái tiếng Anh. Gọi ~T^n~ là xâu được tạo ra bằng cách nối ~n~ xâu ~T~ lại với nhau. Hãy tìm giá trị nhỏ nhất của ~n~ sao cho ~S~ là một xâu rút gọn của xâu ~T^n~.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng 1: xâu ~S~ với độ dài ~|S|~ ~(1 \le |S| \le 10^6)~;
• Dòng 2: xâu ~T~ với độ dài ~|T|~ ~(1 \le |T| \le 10^5)~.

Dữ liệu đầu ra

Gồm một số nguyên là giá trị ~n~ nhỏ nhất sao cho ~S~ là xâu rút gọn của ~T~. Nếu không tồn tại giá trị ~n~ như vậy thì in ra ~-1~.

Ràng buộc dữ liệu

• 8% điểm dành cho các test có ~S~ và ~T~ chỉ chứa ký tự a;
• 13% điểm khác dành cho các test có ~|S|, |T| \le 100~;
• 21% điểm khác dành cho các test có ~|S| \le 10^4,\ |T| \le 100~;
• 34% điểm khác dành cho các test có ~|T| \le 1000~;
• 24% điểm còn lại không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

INPUT

caa
ac

OUTPUT

3

Giải thích: Ta có: ~T^1 = T =~ ac, ~T^2 =~ acac, ~T^3 =~ acacac; ~n = 3~ là giá trị nhỏ nhất để xâu ~S~ trở thành xâu rút gọn của ~T^n~.

Ví dụ 2

INPUT

cab
acca

OUTPUT

-1

Giải thích: Không tìm được ~n~ nào thoả mãn điều kiện.

Cho dãy ~A = (a_1, a_2, ..., a_n)~. Độ đẹp của dãy ~A~ được định nghĩa là tổng lớn nhất của một đoạn con liên tiếp (có thể rỗng) của dãy. Chẳng hạn, dãy ~A = (-3, 8, 4, -2, 12)~ có độ đẹp bằng ~22~ (đoạn con ~(8, 4, -2, 12)~), dãy ~B = (-1, -2, -3, -4, -5)~ có độ đẹp bằng ~0~ (đoạn con rỗng).

Yêu cầu

Để gia tăng độ đẹp của dãy ~A~, bạn được phép chọn tối đa một đoạn con liên tiếp của dãy và nhân từng phần tử trong đoạn con đó lên ~X~ lần. Xác định độ đẹp lớn nhất có thể đạt được của dãy.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng 1: hai số nguyên ~N, X~ ~(1 \le N \le 4 \times 10^5;\ -100 \le X \le 100)~;
• Dòng 2: ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(|a_i| \le 10^9)~.

Dữ liệu đầu ra

Gồm một số nguyên là độ đẹp tối đa của dãy ~A~ sau khi thực hiện không quá một thao tác nói trên.

Ràng buộc dữ liệu

• 20% điểm dành cho các test có ~1 \le N \le 50~;
• 30% điểm khác dành cho các test có ~1 \le N \le 300~;
• 20% điểm khác dành cho các test có: ~a_i \ge 0 \ \forall\ i~;
• 30% điểm còn lại không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

INPUT

5 -2
-3 8 -2 1 -6

OUTPUT

22

Giải thích: Thực hiện thao tác với đoạn ~[-2, 1, -6]~ thu được dãy ~[-3, 8, \underline{4, -2, 12}]~. Dãy này có độ đẹp là ~22~, đây là độ đẹp lớn nhất có thể đạt được.

Ví dụ 2

INPUT

8 -4
1 2 1 1 2 0 0 7

OUTPUT

14

Giải thích: Không cần thực hiện thao tác nào.

Ví dụ 3

INPUT

5 10
-1 -2 -3 -4 -5

OUTPUT

0