CaiWinDao maintains scholarship

Chào mừng ngày mà ami lẫn cuom1999 tụt xuống div 2 codeforces, ami quyết đặt biệt danh cho cuom1999 là một xâu kí tự \(S\). Nhận thấy mình không xứng đáng với món quà này, cuom1999 quyết định tự phạt mình bằng cách bỏ đi một kí tự trong \(S\) để thứ tự từ điển của xâu kết quả là nhỏ nhất có thể. Vì chưa hoàn hồn sau khi bị giáng xuống div 2, các bạn hãy thay cuom1999 thực hiện hình phạt nhé.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) là độ dài xâu \(S\) của ami. Dòng tiếp theo chứ xâu \(S\) độ dài đúng bằng \(n\).

Output

• In ra 1 dòng là xâu \(T\) có thứ tự từ điển nhỏ nhất sau khi xoá một kí tự trong \(S\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(2 \leq n \leq 10^3\)
• Subtask \(2\) (\(70\%\) số điểm): \(2 \leq n \leq 10^5\)

Example

5 

3

CaiWinDao đang ở trong lớp Tâm Lý Học. Thầy giáo bày ra một trò chơi tâm lý như sau: Trên bàn có \(3\) nút bấm màu đỏ, xanh, vàng. Trên mỗi nút có một con số. Mỗi lần ấn nút, con số trên nút đó sẽ tăng thêm \(1\) đơn vị. Thầy giáo sẽ gọi từng sinh viên lên và mỗi sinh viên phải nhấn đúng \(2\) trong \(3\) nút. Mục tiêu của trò chơi là làm sao cho \(3\) con số trên bằng nhau. Là một sinh viên chuyên ngành Khoa Học Máy Tính, CaiWinDao ngay lập tức nghĩ đến bài toán: Cần ít nhất bao nhiêu sinh viên để đạt được mục đích đề ra? Tất nhiên, anh cũng nhanh chóng giải ra bài toán trong vỏn vẹn \(2004\) ms. Các bạn có thể làm được tốt hơn không?

Input

• Gồm một dòng có 3 số tự nhiên \(a,b,c\) là \(3\) con số ban đầu được ghi tương ứng trên các nút đỏ, xanh, vàng.

Output

• In ra một số nguyên, là số sinh viên ít nhất cần thiết. Nếu không có cách nào đạt được mục đích thì in ra \(−1\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(0 \leq a,b,c \leq 30\).
• Subtask \(2\) (\(30\%\) số điểm): \(0 \leq a,b,c \leq 10^6\).
• Subtask \(3\) (\(40\%\) số điểm): \(0 \leq a,b,c \leq 10^{18}\).

Example

3 4 5

3

3 3 3 

0 

Trong một tiết học Nhập môn Tài chính, thầy giáo của CaiWinDao thách đố cả lớp: với một lượng tiền đúng \(C\) đồng thì có thể mua về được tối đa bao nhiêu bộ bài? Biết rằng đơn giá của mỗi bộ bài ở ngoài cửa hàng là \(p\) đồng, và việc mua bán các bộ bài phải chịu đánh thuế hai lần: cứ mua mỗi \(n_1\) bộ bài thì ta phải chịu đúng \(t_1\) đồng tiền thuế giá trị gia tăng, cứ mua mỗi \(n_2\) bộ bài thì ta phải chịu đúng \(t_2\) đồng tiền thuế tiêu thụ đặc biệt. Ví dụ, nếu \(n_1=2\) và \(n_2=4\) thì khi muốn mua \(4\) bộ bài ta phải chịu tổng cộng \(2 \times t_1 + t_2\) đồng tiền thuế.

Vì cách tính thuế quá chồng chéo và phức tạp nên CaiWinDao đành đầu hàng thầy giáo và nhờ đến sự trợ giúp của các bạn. Hãy giúp CaiWinDao tính xem có thể mua tối đa bao nhiêu bộ bài với \(C\) đồng nhé!

Input

• Dòng đầu chứa số nguyên dương \(T \leq 10\) là số lượng câu hỏi.

• \(T\) dòng sau, mỗi dòng chứa sáu số nguyên dương \(C, p, n_1, n_2, t_1\) , và \(t_2\) thể một câu hỏi từ thầy giáo của CaiWinDao.

-Dữ liệu luôn đảm bảo \(1 \leq p,t_1,t_2 \leq 1000, 1 \leq n_1 < n_2 \leq 1000\)

Output

• Gồm \(T\) số nguyên in trên \(T\) dòng riêng biệt là kết quả cho câu hỏi tương ứng.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(C \leq 10^6\).
• Subtask \(2\) (\(60\%\) số điểm): \(C \leq 10^{15}\).

Example

1
80 10 2 4 10 20 

4

Cho hai xâu độ dài bằng nhau \(s_1,s_2\) và hai nút bấm thần kỳ: nút màu xanh khi bấm vào sẽ giúp xóa đi một ký tự đầu của xâu \(s_1\) và một ký tự cuối của xâu \(s_2\), nút màu đỏ khi được bấm sẽ giúp xóa đi một ký tự đầu của xâu \(s_2\) và một ký tự cuối của xâu \(s_1\). Hỏi nếu muốn thu được hai xâu bằng nhau thì ta phải bấm các nút trên ít nhất bao nhiêu lần?

Input

• Dòng đầu chứa số nguyên dương \(n\) thể hiện độ dài của \(s_1\) và \(s_2\).

• Dòng thứ hai và thứ ba lần lượt chứa xâu \(s_1\) và xâu \(s_2\) chỉ gồm các ký tự latin in thường.

Output

• Đưa ra một số nguyên duy nhất là số lần bấm nút để có thể thu được hai xâu bằng nhau. Dữ liệu đảm bảo tồn tại một cách bấm nút để đưa cả hai xâu về cùng bằng một xâu khác rỗng.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 300\).
• Subtask \(2\) (\(60\%\) số điểm): \(n \leq 3000\).

Example

3
abc
cba 

2

Gọi \(\pi=\left(p_1, p_2,..., p_n\right)\) là một hoán vị của \((1, 2,...,n)\), một cặp chỉ số \((i, j)\) được gọi là nghịch thế nếu \(i < j\) nhưng \(p_i > p_j\).

Cho một hoán vị \(\pi_0\) và số nguyên dương \(k\), xét \(k\) hoán vị liên tiếp \(\pi_0\), \(\pi_1\),..., \(\pi_{k-1}\) kể từ hoán vị \(\pi_0\), hãy tính tổng \(f(\pi_0)+f(\pi_1)+...+f(\pi_{k-1})\) với \(f(\pi)\) là số lượng cặp nghịch thế trong hoán vị \(\pi\).

Input

• Dòng đầu chứa hai số nguyên dương \(n\), \(k\) lần lượt là kích thước của hoán vị \(\pi_0\) và số lượng hoán vị liên tiếp cần xét.

• Dòng tiếp theo chứa \(n\) số nguyên dương \(p_1\), \(p_2\),..., \(p_n\) mô tả hoán vị \(\pi_0\).

• Dữ liệu đảm bảo luôn tồn tại ít nhất \(k\) hoán vị hợp lệ kể từ hoán vị \(\pi_0\) trở đi.

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n\leq 10^3, k\leq 10\).
• Subtask \(2\) (\(40\%\) số điểm): \(n\leq 10^5, k\leq 10\).
• Subtask \(3\) (\(20\%\) số điểm): \(n\leq 10^5, k\leq 10^5\).

Example

5 4
1 2 3 4 5

4