TDZ đang tham gia một contest trên trang web HNOJ. Contest này gồm ~N~ bài, mỗi bài có điểm tối thiểu là ~2~ và điểm tối đa là ~5~.

Tuy nhiên, TDZ lại gặp vài vấn đề:

• Nếu điểm của TDZ vượt quá ~k~, cậu sẽ bị chọn đi thi HSG, tuy nhiên cậu lại rất lười và thích ở nhà chơi game hơn là thi cử.
• Nếu điểm của TDZ thấp hơn ~k~, mẹ của cậu sẽ cảm thấy rất buồn.

Vì vậy, TDZ quyết định sẽ đạt được chính xác ~k~ điểm trong contest.

Thực ra cậu là một thiên tài xuất chúng ẩn dật nên có thể tự quyết định mình được bao nhiêu điểm mỗi bài. Nhưng cậu lại rất ghét việc đạt điểm thấp mỗi bài, nên cậu sẽ cố gắng hạn chế việc bị ~2~ điểm nếu có thể.

Hãy giúp TDZ tính xem cậu cần phải đạt tối thiểu bao nhiêu điểm ~2~ trong contest để điểm cả contest đạt được chính xác ~k~ điểm.

Input

Gồm một dòng chứa hai số nguyên ~N~ và ~k~. (~1 \le N \leq 50~; ~2 \times N \le k \le 5 \times N~)

Output

Số bài tối thiểu trong contest phải đạt ~2~ điểm để TDZ có thể đạt được chính xác ~k~ điểm.

Sample Test 1

Input:

4 8

Output:

4

Note: TDZ bắt buộc phải đạt ~2~ điểm cả ~4~ bài để cả contest được ~8~ điểm.

Sample Test 2

Input:

4 10

Output:

2

Note: TDZ có thể đạt ~2~ điểm ở hai bài đầu và ~3~ điểm ở hai bài còn lại.

Sample Test 3

Input:

1 3

Output:

0

Note: TDZ chỉ đạt ~3~ điểm cho một bài duy nhất trong contest.

Farmer John nuôi ~N~ giống bò (~1\le N\le 1000~), được đánh số từ ~1~ đến ~N~. Một số cặp giống bò có mối quan hệ thân thiện hơn các cặp khác, và đặc điểm này có thể được mô tả dễ dàng dựa trên mã số giống: giống ~a~ và ~b~ được coi là thân thiện nếu ~|a-b|\le 4~, và không thân thiện nếu khác.

Một con đường dài chạy qua trang trại của Farmer John. Có một chuỗi gồm ~N~ cánh đồng ở một bên của con đường (mỗi cánh đồng dành riêng cho một giống bò), và một chuỗi gồm ~N~ cánh đồng ở bên kia con đường (cũng mỗi cánh đồng dành cho một giống bò). Để giúp các con bò qua đường an toàn, Farmer John muốn vẽ các lối đi bộ băng qua đường. Mỗi lối đi bộ này nên nối một cánh đồng ở một bên của con đường với một cánh đồng ở bên kia, sao cho hai cánh đồng có mã số giống bò thân thiện (các con bò có thể lạc vào cánh đồng của giống khác, miễn là giống đó thân thiện). Mỗi cánh đồng chỉ có thể có tối đa một lối đi bộ nối vào (nghĩa là các lối đi bộ không giao nhau tại các đầu nối).

Hãy giúp Farmer John xác định số lượng tối đa các lối đi bộ "thân thiện" mà ông có thể vẽ trên con đường sao cho không có hai lối đi nào giao nhau.

Input

• Dòng đầu tiên chứa số nguyên ~N~.
• ~N~ dòng tiếp theo mô tả thứ tự, theo mã số giống, của các cánh đồng ở một bên của con đường; mỗi mã số giống là một số nguyên trong khoảng từ ~1~ đến ~N~.
• ~N~ dòng cuối cùng mô tả thứ tự, theo mã số giống, của các cánh đồng ở bên kia con đường. Mỗi mã số giống xuất hiện đúng một lần trong mỗi thứ tự.

Output

In ra một số nguyên duy nhất là số lượng lối đi bộ "thân thiện" không giao nhau tối đa mà Farmer John có thể vẽ qua con đường.

Example

Sample Input 1

6
1
2
3
4
5
6
6
5
4
3
2
1

Sample Output 1

5

Các nghiện thủ đang bị nhốt trong căn phòng có 1 mật mã được mã hóa trong mảng ~A~ có độ dài ~n~. Bởi muốn nghiện Liên Quân, thần đồng đã sai người tìm và giải mã nó. Ta biết được mảng ~A~ có thể chia thành nhiều dãy con liên tiếp (và có ~2^{n-1}~ cách chia ). Với mỗi dãy con được chia, giá trị của dãy con đấy nếu gồm các số từ vị trí ~l~ đến ~r~ là :

• ~r \;– \; l + 1 ~ nếu tổng các số từ ~l~ đến ~r~ lớn hơn hẳn 0.
• 0 nếu tổng các số từ ~l~ đến ~r~ bằng 0.
• ~–(r \;– \; l + 1)~ nếu tổng các số từ ~l~ đến ~r~ nhỏ hơn hẳn 0.

Gọi ~S~ là tổng các giá trị của dãy con trong 1 cách chia. Mã hóa của căn phòng là ~S~ lớn nhất trong tất cả các cách chia. Biết rằng tin Ams 21-24 toàn những feeder liên quân và best tin học, thần đồng muốn nhờ các bạn tìm mật mã trên.

Input

• Dòng đầu tiên gồm số ~n~
• Dòng tiếp theo gồm ~n~ số của mảng ~A~

Output

• In ra một số là giá trị ~S~ lớn nhất tìm được.

Sample Test

Input:

5
-1 -2 3 -1 -1

Output

1

Sample Test 2

Input:

6
-1 2 -3 4 -5 6

Output

6

Sample Test 3

7
1 -1 -1 1 -1 -1 1

Output

-1

Giải thích:

• Test 1 chia thành (-1 -2 ) (3 -1 -1)
• Test 2 chia thành (-1 2 -3 4 -5 6)
• Test 3 chia thành (1 -1 -1 1 -1) (-1 1)

Ràng buộc:

• ~A_i \le 10^9~
• Subtask 1: ~n \le 20~ (30%)
• Subtask 2: ~n \le 5000~ (40%)
• Subtask 3: ~n \le 5*10^5~ (30%)