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).

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 thì 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 là 27 ô (không tính ô đặt quân Hậu, xem giải thích test ví dụ 1).

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

Input

• Dòng 1: số nguyên ~N~ (~1 \le N \le 10^9~) - 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~) - kích thước bàn cờ theo chiều ngang.

Output

Dòng 1: 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~.

Sample Input 1

8
8

Sample Output 1

27

Sample Input 2

3
4

Sample Output 2

9

Subtasks

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

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ị của 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 ~(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 một 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 với ~l = 3~ và ~r = 4~ thì dãy trở thành ~A = (1, 3, 2, 2, 4)~.

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~.

Input

• 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~ với mọi ~i = 1, 2, ..., N~).

Output

Dòng 1: số nguyên là kết quả.

Sample Input 1

5
1 2 3 4 5

Sample Output 1

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]~

Subtasks

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

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".

Cho hai xâu ~S~ và ~T~ chỉ gồm các ký tự chữ cái tiếng Anh thường. 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~.

Yêu cầu: Hãy tìm giá trị nhỏ nhất của ~n~ thỏa mãn điều kiện trên. Nếu không tồn tại giá trị ~n~ như vậy thì in ra -1.

Input

• 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~).

Output

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

Sample Input 1

caa
ac

Sample Output 1

3

Giải thích: Ta có: ~T^1 = T = abc~, ~T^2 = abcabc~, ~T^3 = abcabcabc~. Với ~n = 3~ là giá trị nhỏ nhất sao cho ~S~ là xâu rút gọn của ~T^n~.

Sample Input 2

cab
acca

Sample Output 2

-1

Subtasks

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

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 ~A~. 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).

Để 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 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.

Yêu cầu: Hãy xác định độ đẹ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.

Input

• Dòng 1: hai số nguyên dương ~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~).

Output

Dòng 1: 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.

Sample Input 1

5 -2
-3 8 -2 1 -6

Sample Output 1

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, 4, -2, 12]~. Dãy này có độ đẹp là 22.

Sample Input 2

8 -4
1 2 1 1 2 0 0 7

Sample Output 2

14

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

Sample Input 3

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

Sample Output 3

0

Subtasks

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