Cho n viên đá, viên đá thứ i có độ cao là ~h_i~. Con ếch đang đứng tại viên đá thứ nhất. Tại vị trí thứ i con ếch có thể nhảy sang hòn đá thứ i + 1 hoặc hòn đá thứ i + 2 với chi phí nhảy là |~h_i - h_j~| với j là vị trí đáp của chú ếch.

Yêu cầu: Hãy tìm chi phí ngắn nhất để chú ếch tới được hòn đá thứ n.

Input

• Dòng đầu gồm n là số lượng hòn đá ~(1 \le n \le 10^5)~
• Dòng sau gồm n số, số thứ i thể hiện hi là chiều cao của viên đá thứ i ~(1 \le h_i \le 10^4)~

Output

• Gồm một dòng duy nhất là đáp án cần tìm

Examples

Input

4
10 30 40 20

Output

30

Input

2
10 10

Output

0

Cho n viên đá, viên đá thứ i có độ cao là ~h_i~. Con ếch đang đứng tại viên đá thứ nhất. Tại vị trí thứ i con ếch có thể nhảy sang 1 trong k hòn đá thứ i + 1, i + 2,...,i + k với chi phí nhảy là ~|h_i - h_j|~ với j là vị trí đáp của chú ếch.

Yêu cầu: Hãy tìm chi phí ngắn nhất để chú ếch tới được hòn đá thứ n.

Input

• Dòng đầu gồm n là số lượng hòn đá và số k ~(1 \le n \le 10^5, 1 \le k \le 100)~
• Dòng sau gồm n số, số thứ i thể hiện hi là chiều cao của viên đá thứ i ~(1 \le hi \le 10^4)~

Output

• Gồm một dòng duy nhất là đáp án cần tìm

Examples

Input

5 3
10 30 40 50 20

Output

30

Input

3 1
10 20 10

Output

20

Note

Ở ví dụ 1 chú ếch sẽ nhảy 1 -> 2 -> 5 với chi phí là |10 - 30| + |30 - 20| = 30

P/S: Nếu có nhiều xâu con chung cùng độ dài và dài nhất, hãy in ra xâu cuối cùng tìm thấy

Output:

• Dòng 1: Ghi số nguyên s là số lượng các phần tử của dãy con tìm được
• Dòng 2: Ghi s số nguyên là các phần tử trong dãy con tìm được.

Example

Input:

10
10 100 20 1 2 50 70 80 3 60

Output:

5
1 2 50 70 80

Cho một dãy số nguyên dương ~a_1, a_2,... a_N, 0 \le a_i \le 32000~. Hãy tỉa bớt một số ít nhất các phần tử của dãy số nguyên đó và giữ nguyên thứ tự các phần tử còn lại sao cho dãy số còn lại là một dãy chỉ bao gồm các số nguyên tố tăng dần. Ta gọi dãy số nguyên tố tăng dần còn lại sau khi đã tỉa bớt một số phần tử là dãy con của dãy đã cho.

Input:

- Dòng đầu ghi số N là số phần tử (1 ≤ N ≤ 10000)
- Dòng tiếp theo ghi N số là các số nguyên của dãy.

Output:

- Dòng 1: Ghi số nguyên số lượng phần tử của dãy con cực đại.
- Dòng 2: Ghi các phần tử trong dãy con đó (theo thứ tự tăng dần), mỗi phần tử cách nhau ít nhất 1 dấu cách.

Example

Input:

10
2 100 3 1 2 50 7 80 13 60

Output:

4
2 3 7 13

Bờm chơi trò chơi điện tử Lucky Luke đến màn phải điều khiển Lucky leo lên một cầu thang gồm n bậc. Các bậc thang được đánh số từ 1 đến n từ dưới lên trên. Lucky có thể đi lên một bậc thang, hoặc nhảy một bước lên hai bậc thang. Tuy nhiên một số bậc thang đã bị thủng do cũ kỹ và Lucky không thể bước chân lên được. Biết ban đầu, Lucky đứng ở bậc thang số 1 (bậc thang số 1 không bao giờ bị thủng). Chơi đến đây, Bờm chợt nảy ra câu hỏi: có bao nhiêu cách để Lucky leo hết được cầu thang? (nghĩa là leo đến bậc thang thứ n). Bờm muốn nhờ bạn trả lời câu hỏi này.

Input

• Dòng đầu tiên: gồm 2 số nguyên n và k, là số bậc của cầu thang và số bậc thang bị hỏng ~(0 \le k < n \le 10^5)~.
• Dòng thứ hai: gồm k số nguyên cho biết chỉ số của các bậc thang bị hỏng theo thứ tự tăng dần.

Output

• In ra phần dư của số cách Lucky leo hết cầu thang khi chia cho 14062008

Examples

Input

4 2
2 3

Output

0

Input

90000 1
49000

Output

4108266

Vườn zayzen123 có một cây khế ngọt, năm lần bảy lượt chim thần cứ đến xin khế, hôm qua chim thần lại đến. Lần này chim thần chở zayzen123 đến đảo đá quý. Trên hòn đảo bây giờ chỉ còn N loại đá quý. Loại thứ i có trọng lượng là ~w_i~ có giá trị là ~v_i~. zayzen123 mang theo túi "mười lăm" gang có thể chứa tối đa trọng lượng là M. Hỏi tổng giá trị tối đa của các viên đá quý mà zayzen123 có thể mang về là bao nhiêu, biết rằng zayzen123 chỉ được phép lấy mỗi loại một viên?

Input:

• Dòng đầu tiên ghi hai số N và M ~(1 ≤ N,M ≤ 1000)~.

• N dòng tiếp theo, dòng thứ i ghi ba số ~w_i , v_i~ lần lượt là trọng lượng, giá trị và số lượng của loại đá quý thứ i ~(0 ≤ w_i, v_i ≤ 10^3)~

Output:

• Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất mà zayzen123 em có thể mang về.

Example:

input

3 50
10 60
20 100
30 120

output

220

Khác với lần trước, lần này chim thần chở zayzen123 đến một hòn đảo khác với vô số đá quý. Trên hòn đảo bây giờ có N loại đá quý. Loại thứ i có trọng lượng là ~w_i~ có giá trị là ~v_i~ và có số lượng là ~a_i~. Lần này Zayzen123 mang theo túi "năm trăm gang" có thể chứa tối đa trọng lượng là M. Hỏi tổng giá trị tối đa của các viên đá quý mà zayzen123 có thể mang về là bao nhiêu?

Input:

• Dòng đầu tiên ghi hai số N và M ~(1 ≤ N,M ≤ 1000)~.

• N dòng tiếp theo, dòng thứ i ghi ba số ~w_i , v_i , a_i~ lần lượt là trọng lượng, giá trị và số lượng của loại đá quý thứ i ~(0 ≤ w_i, v_i , a_i ≤ 10^3)~

Output:

• Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất mà zayzen123 em có thể mang về.

Example:

input

3 4 
1 4 2 
2 7 2 
3 6 1   

output

15

Năm lần bảy lượt chim thần đến nhà Zayzen123 để xin khế. Lần này trên cây chỉ còn 1 quả cuối cùng. Zayzen123 muốn giữ lại để chấm muối ớt vì từ đầu mùa đến giờ đã có quả nào bỏ vào bụng đâu. Khóc lóc, van xin một hồi lâu, cuối cùng Zayzen123 cũng xiêu lòng và đem quả khế cuối cùng cho chim thần. Lần này chim thần trả công cho Zayzen123 rất hậu hĩnh, chim thần chở zayzen123 đến một hòn đảo khác với vô số đá quý. Trên hòn đảo bây giờ có N loại đá quý. Loại thứ i có trọng lượng là ~w_i~ có giá trị là ~v_i~ và có số lượng mỗi loại nhiều vô kể. Khác với lần trước, lần này Zayzen123 mang theo túi "năm trăm gang" có thể chứa tối đa trọng lượng là M. Hỏi tổng giá trị tối đa của các viên đá quý mà zayzen123 có thể mang về là bao nhiêu? Biết rằng, zayzen1234 có thể chọn 1 loại đá quý với số lượng tuỳ thích.

Input:

• Dòng đầu tiên ghi hai số N và M ~(1 ≤ N,M ≤ 1000)~.

• N dòng tiếp theo, dòng thứ i ghi hai số ~w_i , v_i~ lần lượt là trọng lượng và giá trị của loại đá quý thứ i ~(0 ≤ w_i, v_i ≤ 10^3)~

Output:

• Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất mà zayzen123 em có thể mang về.

Example:

input

5 15
12 4
2 2
1 1
1 2
4 10

output

36

P/S:

Vì chưa rõ ý đồ giới hạn của tác giả nên test chấm chỉ mang tính chất tham khảo, test đang rất yếu.**

Ràng buộc:

• ~(1 ≤ N,M ≤ 1000; 0 ≤ u_i, k_i ≤ 10^3)~

Cho một hình chữ nhật kích thước 2xN. Hãy đếm số cách lát các viên gạch nhỏ kích thước 1x2 và 2x1 vào hình trên sao cho không có phần nào của các viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật không được lát.

Input

• Gồm nhiều test, dòng đầu ghi số lượng test T ~(T \le 10^6)~.
• T dòng sau mỗi dòng ghi một số N ~(1 \le N \le 10^6)~.

Output

• Gồm T là T kết quả cần tìm chia dư cho ~10^9 + 7~

Example

Input

3
1
2
3

Output

1
2
3

Dãy số nguyên ~a_1, a_2,…,a_n~ được gọi là dãy lõm nếu nó tăng dần từ ~a_1~ tới ~a_i~ nào đó, rồi giảm dần tới ~a_n~.

Ví dụ: dãy 2 4 5 4 3 1 là dãy lõm.

W là 1 dãy các số nguyên dương. Nó có các đặc điểm sau:

• Độ dài của dãy là 1 số lẻ: ~L = 2 * N + 1~

• ~N + 1~ số nguyên đầu tiên của dãy tạo thành 1 dãy tăng

• ~N + 1~ số nguyên cuối của dãy tạo thành 1 dãy giảm

• Không có 2 số nguyên nào cạnh nhau trong dãy có giá trị bằng nhau

Ví dụ: 1, 2, 3, 4, 5, 4, 3, 2, 1 là 1 dãy W độ dài 9. Tuy nhiên, dãy 1, 2, 3, 4, 5, 4, 3, 2, 2 không là 1 dãy W

Yêu cầu: Trong các dãy con của dãy số cho trước, tìm dãy W có độ dài dài nhất.

Input

• Dòng 1: số nguyên dương ~N(N \le 10^3)~, độ dài dãy số.
• Dòng 2: N số nguyên dương ~a_i (a_i ≤ 10^9)~.

Output

• Ghi 1 số nguyên dương duy nhất là độ dài dãy W dài nhất.

Examples

Input

10
1 2 3 4 5 4 3 2 1 10

Output

9

Input

19
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1

Output

9

Các học sinh khi đến thực tập trong phòng máy tính thường hay chơi trò chơi điện tử trên mạng. Để ngăn ngừa, người trực phòng máy đã ngắt tất cả các máy tính ra khỏi mạng và xếp chúng thành một dãy trên một cái bàn dài và gắn chặt máy xuống mặt bàn rồi đánh số thứ tự các máy từ 1 đến N theo chiều từ trái sang phải.

Các học sinh tinh nghịch không chịu thua, họ đã quyết định tìm cách nối các máy trên bàn bởi các đoạn dây nối sao cho mỗi máy được nối với ít nhất một máy khác. Để tiến hành công việc này, họ đã đo khoảng cách giữa hai máy liên tiếp. Bạn hãy giúp các học sinh này tìm cách nối mạng thoả mãn yêu cầu đặt ra sao cho tổng độ dài cáp nối phải sử dụng là ít nhất.

Input

• Dòng đầu tiên chứa số lượng máy N ~(2 \le N \le 10^5)~.
• Dòng thứ i trong số N - 1 dòng tiếp theo chứa các khoảng cách từ máy i đến máy i + 1 (i = 1, 2, ..., N - 1). Giả thiết rằng khoảng cách từ máy 1 đến máy N không vượt quá ~10^6~.

Output

• Gồm một dòng duy nhất là đáp án cần tìm

Example

Input

6
2
2
3
2
2

Output

7

Note

• Nối máy 1 -> 2, 3 -> 4, 5 -> 6

• Tổng là 2 + 3 + 2 = 7

Nhà trường có một phòng hội trường. Có những yêu cầu muốn sử dụng phòng hội trường này, mỗi yêu cầu cho biết thời điểm bắt đầu và thời điểm kết thúc. Nhà trường có thể chấp nhận hoặc từ chối đối với một yêu cầu.

Yêu cầu: hãy giúp nhà trường chọn các yêu cầu sử dụng hội trường sao cho tổng thời gian hội trường được sử dụng là lớn nhất.

Input:

• Dòng đầu tiên chứa một số nguyên dương ~N(N \le 10000)~ số yêu cầu.

• Mỗi dòng trong số N dòng tiếp theo chứa 2 số nguyên dương p và k ~(0 \le p < k \le 30000)~, mô tả một yêu cầu bắt đầu tại thời điểm p và kết thúc tại thời điểm k.

Output:

• Gồm một dòng duy nhất là tổng thời gian lớn nhất mà hội trường được sử dụng

Example:

Input:

12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20

Output:

16

Trung tâm tính toán hiệu năng cao nhận được đơn đặt hàng của n khách hàng. Khách hàng i muốn sử dụng máy trong khoảng thời gian từ ~a_i~ đến ~b_i~ và trả tiền thuê là ~c_i~.

Yêu cầu: Hãy bố trí lịch thuê máy để tổng số tiền thu được là lớn nhất mà thời gian sử dụng máy của 2 khách hàng bất kì được phục vụ đều không giao nhau (cả trung tâm chỉ có một máy cho thuê).

Input

• Dòng đầu tiên chứa một số nguyên dương n (~n \le 10^4~)
• Mỗi dòng trong số n dòng tiếp theo, dòng thứ i chứa 3 số nguyên dương ~a_i, b_i, c_i (0 \le a_i < b_i \le 10^5, 1 \le c_i \le 10^5)~

  Output

Gồm một dòng duy nhất là tổng số tiền thu được lớn nhất

Examples

Input

3
4 11 10
1 5 4
5 10 5

Output

10

Input

4
4 11 1
1 5 1
5 10 1
1 100 1

Output

2

Minh là một học sinh rất yêu thích lập trình, em đã tạo ra một Game X nhằm giúp người chơi phát triển tư duy toán học. Game được mô tả như sau: cho trước n tấm thẻ hình chữ nhật được đánh số thứ từ 1 đến n, tấm thẻ thứ i ghi một số nguyên dương n. Mỗi lượt chơi, người chơi cần chọn số lượng tấm thẻ nhiều nhất có thể và tuân thủ các quy tắc của trò chơi như sau: Chọn ra một số tấm thẻ xếp thành hàng ngang, sao cho thứ tự tấm thẻ tăng dần theo chỉ số từ trái sang phải. Tấm thẻ i, j ~(1 \le i, j \le n)~ xếp cạnh nhau cần thỏa các điều kiện:

• ~0 < |i - j| \le 10~

• ~|a_j - a_i| > 0~

• ~|a_j - a_i|~ là bình phương của một số tự nhiên

Yêu cầu: Cho biết số lượng tấm thẻ nhiều nhất mà người chơi có thể chọn được trong mỗi lượt chơi

Input

• Dòng thứ nhất gồm n ~(1 \le n \le 10^5)~
• Dòng thứ i trong n dòng tiếp theo chứa số nguyên dương ai ~(1 \le a_i \le 10^9)~

Output

• Gồm một dòng duy nhất là đáp án cần tìm

  Example

Input

7
2
6
2
31
22
11
26

Output

5

Note

• Dãy dài nhất có 5 phần tử là: 2, 6, 31, 22, 26

Ngày 23 tháng 11 năm 2024, Trường đại học Quảng Bình có tổ chức kỳ thi tin học trẻ cho các bạn học sinh trung học phổ thông giao lưu với nhau. Các bạn học sinh THCS cũng háo hức tham gia thử sức dẫu biết là lấy trứng chọi với đá. Có ~N~ học sinh tham gia kỳ thi lập trình được sắp xếp vào 1 dãy máy tính nằm trên một đường thẳng và được đánh số từ 1 đến ~N~ (bạn thứ nhất được đánh số thứ tự là 1). Trong danh sách các bạn tham gia thì số lượng bạn nữ ít hơn khá nhiều so với số lượng bạn nam. Vì thế, ban tổ chức đã không xếp 3 bạn nữ cùng ngồi kế nhau.

Yêu cầu: Hãy cho biết có bao nhiêu cách xếp hàng thỏa mãn điều kiện trên

Input:

• Được cho bởi tệp tht.inp gồm 1 dòng duy nhất chứa số ~N~ (~1 ≤ N ≤ 64~)

Output

• Được cho bởi tệp tht.out gồm 1 dòng chứa số nguyên duy nhất là kết quả tìm được.

Example

Input

3

Output

7

Note

• Với N = 3, giả sử ký hiệu số 0 là bạn nam, số 1 là bạn nữ thì có các cách xếp hàng như sau: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0)

Scoring

• 25% test ứng với 1 ≤ N ≤ 20
• 75% test ứng với 20 < N ≤ 64

Một xâu nhị phân ~S~. Ta có thể thao tác trên xâu này bằng cách:

• Chọn 1 số ~p~ bất kì ~(1 \le n)~
• Chặt xâu ~S~ đang xét ra thành 2 xâu con ~S_x[1 ... p]~, ~S_y[p + 1 ... n]~
• Lặp lại các thao tác trên các xâu con được tạo ra

Chú ý: ~n~ là độ dài của xâu ~S~ hiện tại

Một xâu nhị phân được định nghĩa là Hoàn Hảo khi và chỉ khi tất cả các số 0 đến đứng sau số 1

Yêu Cầu: Hãy đếm số lần biến đổi nhỏ nhất để biến đổi xâu ~S~ thành một xâu Hoàn Hảo.

INPUT

• Gồm một dòng là xâu ~S~ ~(|S| \le 10^7)~

OUTPUT

• Gồm một số nguyên dương là yêu cầu của bài toán

SUBTASKS

• Subtask 1 (20%): ~|S| \le 100~
• Subtask 2 (80%): ~|S| \le 10^7~

SAMPLE

Input

1000111011

Output

3

Explanation

Ta chọn các số x lần lượt là:

x = 7: 1000111|011

x = 4: 1000|111|011

x = 1: 1|000|111|011

-> Sắp xếp lại: 000|011|111|1

-> Thỏa mãn yêu cầu đề bài

Trong cuộc thi THT vừa rồi, Tèo đã đạt được giải khá cao, vượt chỉ tiêu mà Tèo và thầy đội tuyển đặt ra.

Nên thầy quyết định cho Tèo quyền chọn ra một số món quà cho bản thân mình.

Thầy đội tuyển chuẩn bị ~n~ món quà được đánh số từ ~1~ đến ~n~, phần thưởng thứ ~i~ ~(i \le n)~ sẽ có giá trị là ~a_i~.

Vì thầy đội tuyển đâu có ngu mà cho Tèo chọn hết. Nên thầy sẽ đưa ra một luật lệ rằng:

• Tèo không thể chọn quá 2 món quà liên tiếp nhau.

Nhưng Tèo cũng đâu phải dạng tép riu đâu. Vừa tài năng vừa tham lam nên Tèo trong một vài giây tính toán đã biết được tổng ~S~ lớn nhất mà mình có thể nhận được.

Tuy tính toán nhanh là vậy, nhưng Tèo lại không quá tin vào kết quả của mình.

Nên Tèo muốn nhờ bạn viết một chương trình kiểm tra xem tổng ~S~ lớn nhất của dãy ~a_i~ ~(i \le n)~ có thể tạo ra là bao nhiêu. Từ đó cậu có thể so sánh với kết quả của mình.

Lưu ý: ~S~ là tổng giá trị của các mòn quà được chọn.

Yêu Cầu: Tìm tổng ~S~ lớn nhất.

INPUT

• Dòng đầu số nguyên dương ~n~ ~(n \le 10^5)~
• Dòng tiếp theo là dãy nguyên dương ~A~ gồm ~n~ phần tử ~(1 \le A_i \le 10^{6})~

OUTPUT

• Gồm một số nguyên dương là yêu cầu của bài toán

SUBTASKS

• Subtask 1 (20%): ~n \le 20~
• Subtask 2 (50%): ~n \le 10^4~
• Subtask 3 (30%): ~n \le 10^5~

SAMPLE

Input

5
5 4 1 3 4

Output

16

Explanation

Các món quà ta có thể chọn để đạt được Smax là:

S = a[1] + a[2] + a[4] + a[5]
  = 5 + 4 + 3 + 4
  = 16

Cho dãy a gồm n số ~a_1, a_2, ..., a_n~, hãy đếm số lượng dãy con có tổng là ~S~, vì đáp án có thể rất lớn hãy in chia dư cho ~10^9 + 7~

Input

• Dòng đầu gồm ~n~ và ~S~ (~1 ≤ n ≤ 100, 1 ≤ S ≤ 1000~)
• Dòng tiếp theo gồm ~n~ số, số thứ ~i~ là giá trị của ~a_i~ (~1 ≤ ai ≤ S~)

Output

• Gồm một dòng duy nhất là đáp án cần tìm

Example

input

3 2
1 1 1

output

3

Example

Input

3 9
2 3 5

Output

8

Nhân dịp kỷ niệm ngày thành lập Đoàn thanh niên cộng sản Hồ Chí Minh, lớp bạn Tèo có tổ chức đi cắm trại ở khu du lịch sinh thái. Lớp của Tèo có N bạn, trong đó bạn thứ i được đánh giá có độ vui vẻ là 1 số nguyên ~a_i~. Để thuận tiện cho việc quản lý và phân công nhiệm vụ, cô giáo yêu cầu bạn Tèo chọn ra 1 nhóm bạn trong lớp có tổng độ vui vẻ là K.

Yêu cầu: Hãy giúp bạn Tèo tính xem có bao nhiêu cách chọn từ trong lớp một nhóm bạn có tổng độ vui vẻ đúng bằng K theo yêu cầu của cô giáo.

Lưu ý: Mỗi người cũng được xem như 1 nhóm bạn.

Input:

• Dòng đầu tiên: chứa 2 số nguyên N, K được ghi cách nhau 1 ký tự trắng.~( 1\le N \le 25, -10^5 \le K \le 10^5)~
• Dòng tiếp theo chứa N số nguyên ~a_i~ là độ vui vẻ của bạn thứ i ~(1 \le i \le N)~; các số lần lượt ghi cách nhau 1 ký tự trắng. ~(-10^4 \le a_i \le 10^4)~

Output:

• Ghi ra một số nguyên duy nhất là số cách chọn một nhóm bạn có tổng độ vui vẻ bằng k.

Example:

Input:

5  4 
2 3 2 4 2

Output:

4

Cho một dãy các số nguyên A có N phần tử, hãy tìm đoạn con gồm các phần tử liên tiếp có tổng lớn nhất của dãy A này.

Input:

• Dòng đầu chứa số N.
• Dòng thứ 2 chứa N số, là miêu tả dãy A.

Output:

• Tổng của đoạn con có tổng lớn nhất tìm được.

Example:

Input

6
1 2 3 -1 -1 -1

Output

6

Constraint:

~0 < N \le 10^5; |A_i| \le 10^9~

Người ta định nghĩa: Một xâu được gọi là xâu đối xứng (palindrome) nếu như xâu đó đọc từ trái sang phải hay đọc từ phải sang trái đều như nhau. Cho một xâu ~S~, người ta định nghĩa một xâu con của ~S~ là xâu thu được khi xóa đi một số kí tự từ xâu ~S~ ban đầu.

Yêu cầu: Hãy tìm số kí tự ít nhất cần xoá để xâu con của ~S~ là xâu đối xứng ?

Input

• Dòng 1: Chứa xâu ~S~ chỉ gồm các chữ cái in thường, giới hạn độ dài không quá ~2000~.

Output

• Dòng 1: Ghi ra số lượng ký tự cần xoá ít nhất để thu được xâu con đối xứng trích từ xâu S.

Example

Input:

lmevxeyzl

Output:

4

Shinoz cho bạn một dãy ~A~ gồm ~n~ phần tử và muốn bạn hãy sắp xếp mảng lại thành một mảng không giảm.

Nhưng Shinoz lại thấy bài toán này khá là đơn giản nên cậu ta sẽ cho bạn biến đổi mảng ~A~ như sau:

• Chọn 2 chỉ số ~i~ và ~j~ ~(1 \le i < j \le n)~

• Xóa 2 phần tử ~A_i~ và ~A_j~

• Chèn vào mảng tổng của ~A_i~ và ~A_j~ ở vị trí bất kì

Hãy lặp lại thao tác này cho đến khi dãy ~A~ ban đầu trở thành dãy không giảm.

Yêu cầu: Hãy đếm số lần biến đổi nhỏ nhất để mảng ~A~ trở thành mảng không giảm

INPUT

• Dòng đầu chứa số ~n~ ~(1 \le n \le 2.10^5)~
• Dòng tiếp là dãy ~A~ gồm ~n~ phần tử ~(1 \le A_i \le 10^6)~

OUTPUT

• Gồm một số nguyên dương là yêu cầu của bài toán

SUBTASKS

• Subtask 1 (30%): ~n \le 10^4~
• Subtask 2 (70%): ~n \le 2.10^5~

SAMPLE

Input

5
1 3 2 2 5

Output

1

Explanation

- Ta chọn i = 2 và j = 3

- Xóa A[2] và A[3]

- Chèn vào cuối mảng tổng của A[2] + A[3] = 3 + 2 = 5

-> Mảng sau khi biến đổi: 1 2 5 5

-> Thỏa mãn yêu cầu bài toán là biến đổi thành dãy không giảm

-> Chỉ tốn 1 lần biến đổi

Shinoz đang đi dạo trên phố, bỗng nhiên anh gặp một người mặc đồ đen kì lạ tới bắt chuyện với anh và cho anh một deal là có thể đổi đồng xu ~x~ để đổi lấy ba đồng xu ~x \over 2~, ~x \over 3~ và ~x \over 4~. Shinoz thấy đây là một deal hời vcl, ngại gì mà không đổi.

Lưu ý: Với các số không chia hết, chỉ lấy phần nguyên.

Yêu cầu: Với đồng xu ban đầu có giá trị ~n~, hãy đổi theo cách tối ưu nhất để thu được giá trị lớn nhất.

INPUT

• Dòng đầu tiên gồm số nguyên ~q~ ~(q \le 100)~
• ~q~ dòng tiếp theo là số ~n~ ~(n \le 10^{12})~

OUTPUT

• Gồm ~q~ dòng, mỗi dòng là yêu cầu của bài toán

SAMPLE

Input

2
12
6

Output

13
6

Explanation

Với xu 12 ta có thể đổi ra 3 xu có giá trị lần lượt là 6, 4, 3 và có tổng là 13.

Ta tiếp tục xét xu 6 có thể đổi ra 3 xu có giá trị lần lượt là 3, 2, 1 và có tổng là 6 -> đổi hay không đổi vẫn giữ nguyên

Tương tự với xu:
4: 2 + 1 + 1 = 4 -> Giữ nguyên
3: 1 + 1 + 0 = 2 -> Không nên đổi

Tiếp tục xét cả xu có giá trị 2 và 1 thì ta thấy rõ là không nên đổi

Cho một xâu ~S~, hãy đếm số cách tạo xâu "skibidi" trong xâu ~S~

Yêu cầu: In ra số cách tạo xâu "skibidi" trong xâu ~S~

NOTE: Vì kết quả có thể rất lớn nên hãy in kết quả sau khi chia dư cho ~10^9 + 7~

INPUT

• Gồm một dòng là xâu ~S~ ~(|S| \le 10^5)~

OUTPUT

• Gồm một số nguyên dương là yêu cầu của bài toán

SUBTASKS

• Subtask 1 (50%): ~|S| \le 100~
• Subtask 2 (50%): ~|S| \le 10^5~

SAMPLE

Input

abskxyibzzzicccdiii

Output

3

Cho một bảng A kích thước ~m~ x ~n~(~1 \le m,n,\le 100~), trên đó ghi các số nguyên ~a_{ij}~ (~|a_{ij}|\le 100~). Một người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được).

Quy tắc đi: Từ ô ~(i,j)~ chỉ được quyền sang một trong 3 ô ~(i;j+1); (i-1;j+1) ; (i+1;j+1)~

Input

• Dòng 1: Ghi hai số m, n tương ứng là số hàng và số cột của bảng.
• m dòng tiếp theo, dòng thứ i ghi đủ n số trên hàng của bảng theo đúng thứ tự từ trái qua phải.

Output

• Gồm 1 dòng duy nhất ghi tổng lớn nhất tìm được

Ví dụ

Input

5 7
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7

Output

41

Nhân dịp chào mừng kỷ niệm ngày thành lập Quân đội Nhân dân Việt Nam, Liên đội đã lên kế hoạch tổ chức Hội thi kéo co giữa các lớp trong toàn trường. Theo quy định của Ban tổ chức, số lượng thành viên của mỗi đội thi là không hạn chế và tổng cân nặng của các thành viên tham gia mỗi đội không vượt quá K kilogam. Là lớp trưởng lớp 9A, Tý cũng rất háo hức để chuẩn bị cho đội thi của lớp mình nên đã tìm hiểu rất kỹ về Hội thi. Sau khi tham khảo kinh nghiệm từ các thầy cô, cậu biết được rằng đội nào có tổng chiều cao các thành viên lớn nhất thì thường là đội vô địch. Do đó, Tý cũng rất muốn chọn ra đội thi của lớp mình sao cho tổng chiều cao các thành viên trong đội là lớn nhất.
Lớp của Tý có N học sinh được đánh số từ 1 đến N. Cân nặng tương ứng của các thành viên là ~a_1, a_2, ..., a_N~ và chiều cao tương ứng của các thành viên là ~b_1, b_2, ..., b_N~.

Yêu cầu: Hãy lập trình giúp Tý chọn được các thành viên của đội sao cho tổng chiều cao của đội là lớn nhất mà vẫn đảm bảo quy định của Ban tổ chức.

Dữ liệu vào:

Cho trong tệp văn bản KNAPSACK4.INP có cấu trúc như sau:

• Dòng 1: Ghi 2 số nguyên dương N, K (~1 ≤ N ≤ 150, 1 ≤ K ≤ 10^9~).
• Dòng 2: Ghi N số nguyên dương ~a_1, a_2, ... a_N~. (~1 ≤ i ≤ N, 1 ≤ a_i ≤ 10^9~).
• Dòng 3: Ghi N số nguyên dương ~b_1, b_2, ... b_N~. (~1 ≤ i ≤ N, 1 ≤ b_i ≤ 10^3~). Các số trên cùng một dòng được ghi cách nhau một dấu cách.

Dữ liệu ra:

Ghi ra tệp văn bản KNAPSACK4.OUT theo cấu trúc như sau:

• Dòng 1: Ghi một số nguyên dương t duy nhất là tổng chiều cao lớn nhất có thể của đội thi.

Ví dụ:

Input

5 140 
44 50 30 35 46
130 150 120 150 140

Output

440

Giới hạn:

• Có 70% số test tương ứng với 70% số điểm của câu có (~1 ≤ N ≤ 20, 10^5 ≤ K ≤ 10^9~)
• Có 30% số test tương ứng với 30% số điểm của câu có (~100 < N ≤ 150, 1 ≤ K ≤ 10^4~)