Kiến đang ở ô \((1,1)\) và muốn đi đến ô \((n,m)\).

Biết rằng nếu kiến đang ở ô \((x,y)\) thì kiến có thể đi đến \(1\) trong \(2\) ô \((x + 1,y)\) và \((x,y+1)\).

Tính số đường đi kiến có thể đi đến ô \((n,m)\)

Dữ liệu

• \(n,m (1 \le n,m \le 6)\)

Kết quả

• Số đường đi

Sample Input

2 2

Sample Output

2

Cho dãy số nguyên không âm \(a_i (a_i \leq 10^6)\), \(n\) phần tử.

Hãy tìm dãy con liên tiếp dài nhất trong dãy số sao cho số các số xuất hiện trong dãy con đó không vượt quá \(k\).

Input

• \(n,k \leq 5*10^5\)

• n số, \(a_i\).

Output

• Vị trí đầu tiên và vị trí cuối cùng của dãy (nếu có nhiều dãy có cùng độ dài, hãy tìm dãy con có vị trí đầu tiên là nhỏ nhất)

Example

9 3
6 5 1 2 3 2 1 4 5

3 7

HT AIRLINE là một hãng hàng không danh tiếng ở Việt Nam, tuy nhiên, để tồn tại trong cơn bão suy thoái kinh tế, Ban giám đốc quyết định giảm chi phi tiền lương cho phi công càng nhiều càng tốt.

HT airline có tất cả \(N\) phi công (\(N\) là số chẵn), các phi công được đánh số từ 1 đến \(N\) (Phi công 1 là phi công trẻ nhất, phi công \(i\) là phi công có tuổi cao thứ \(i\),… phi công \(n\) là phi công cao tuổi nhất). HT airline cần chính xác \(\dfrac{N}{2}\) phi hành đoàn, mỗi phi hành đoàn gồm 2 phi công (một lái chính và một lái phụ), lái chính phải nhiều tuổi hơn lái phụ. Hợp đồng mà công ty kí với các phi công có 2 điều khoản rõ ràng: tiền lương khi là lái chính và tiền lương khi là lái phụ. Rõ ràng, đối với 1 phi công, tiền lương lái chính bao giờ cũng cao hơn tiền lương khi lái phụ. Tuy nhiên, với một phi hành đoàn, có thể tiền lương của lái chính lại thấp hơn lái phụ.

Để giảm chi phí trả tiền lương, HT phải xác định một cách phân chia tối ưu \(\dfrac{N}{2}\) phi hành đoàn.

Bạn hãy giúp HT viết chương trình xác định số tiền tối thiểu để trả lương cho \(N\) phi công.

Input

• Dòng 1 : Số nguyên dương \(N\), là số phi công ở HT airline (\(2≤N≤10000\); \(N\) là số chẵn).
• \(N\) dòng tiếp theo, dòng thứ \(i\) là thông tin về phi công \(i\) : gồm hai số \(a\) và \(c\) viết cách nhau 1 dấu cách trống, tương ứng là tiền lương khi lái chính và tiền lương khi lái phụ. (\(1≤a≤c≤100.000\))

Output

• Ghi ra một số nguyên duy nhất là tiền lương tối thiểu phải trả cho \(N\) phi công.

Scoring

Example

6
10000 7000
9000 3000
6000 4000
5000 1000
9000 3000
8000 6000

32000

6
5000 3000
4000 1000
9000 7000
11000 5000
7000 3000
8000 6000

33000