Cho một xâu gồm \(m\) loại kí tự khác nhau (chỉ bao gồm các chữ cái tiếng Anh in hoa) và hai loại thao tác xoá như sau:

• Thao tác \(1\): Xoá kí tự đầu hoặc kí tự cuối của xâu;
• Thao tác \(2\): Xoá một kí tự ở giữa xâu.

Yêu cầu: Cho xâu \(S\) gồm \(N\) kí tự, hãy tìm cách sử dụng các thao tác xoá xâu để thoả mãn các điều kiện sau:

• Dùng tối thiểu thao tác \(2\);
• Xâu còn lại chỉ còn đúng \(m \times k\) kí tự;
• Mỗi loại kí tự chỉ xuất hiện đúng \(k\) lần.

Dữ liệu vào từ tệp văn bản DELSTR.INP:

• Dòng đầu tiên chứa hai số \(m, k\) \((2 \le m \le 26)\);
• Dòng tiếp theo chứa xâu \(S\) \((2 \le m \times k \le N \le 2 \times 10^5)\).

Kết quả ghi ra tệp văn bản DELSTR.OUT:

Gồm một số nguyên duy nhất là số thao tác \(2\) ít nhất được sử dụng để thoả mãn yêu cầu đề bài.

Ví dụ

Input

3 2
ABBABCABBCCCBA

Output

1

Giải thích

• Sử dụng thao tác \(1\): Xoá \(3\) kí tự đầu và \(4\) kí tự cuối.
• Sau đó dùng \(1\) lần thao tác \(2\) xoá kí tự \(B\) còn thừa ở giữa.

\(\Rightarrow\) Thu được xâu: ABCABC thoả mãn có đúng \(3 \times 2 = 6\) kí tự và mỗi kí tự xuất hiện đúng \(2\) lần.

Input

3 2
ABABAAACCC

Output

2

Giải thích

• Xoá \(1\) kí tự đầu và \(1\) kí tự cuối, sau đó dùng hai lần thao tác \(2\) xoá kí tự \(A\) còn thừa ở giữa.

Ràng buộc

• Có \(25\%\) số test ứng với \(25\%\) số điểm có \(N \le 20\);
• \(25\%\) số test khác ứng với \(25\%\) số điểm có \(N \le 100\);
• \(25\%\) số test khác ứng với \(25\%\) số điểm có \(N \le 5000\);
• \(25\%\) số test còn lại ứng với \(25\%\) số điểm không có ràng buộc gì thêm.

Trên hệ trục toạ độ \(Oxy\), cho một đa giác lồi được tạo bởi \(N\) điểm có toạ độ nguyên.

Yêu cầu: Hãy tìm hình tứ giác có diện tích lớn nhất được tạo bởi \(4\) trong \(N\) điểm của đa giác lồi đã cho.

Dữ liệu vào từ tệp văn bản QUADIL.INP:

• Dòng thứ nhất ghi số \(N\) \((4 \le N \le 10^4)\) là số đỉnh của đa giác lồi;
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x, y\) \((|x|, |y| \le 10^5)\) biểu diễn toạ độ các đỉnh của đa giác. Thứ tự các đỉnh được liệt kê theo chiều kim đồng hồ.

Kết quả ghi ra tệp văn bản QUADIL.OUT:

Gồm một số duy nhất là diện tích lớn nhất của tứ giác tìm được. Kết quả lấy chính xác \(1\) chữ số sau phần thập phân.

Ví dụ

Input

5
0 2
1 3
2 2
2 0
0 0

Output

4.0

Giải thích

Chọn các đỉnh: \((0, 2), (2, 2), (2, 0), (0, 0)\).

Input

6
4 2
3 3
4 5
6 5
7 3
6 2

Output

6.5

Giải thích

Chọn các đỉnh: \((3, 3), (4, 5), (6, 5), (6, 2)\).

Ràng buộc

• Có \(40\%\) số test ứng với \(40\%\) số điểm có \(N \le 50\);
• \(30\%\) số test khác ứng với \(30\%\) số điểm có \(N \le 200\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm có \(N \le 2000\);
• \(10\%\) số test còn lại ứng với \(10\%\) số điểm không có ràng buộc gì thêm.

Một trò chơi đánh golf trên smartphone được mô phỏng là một lưới ô vuông có kích thước \(R\) dòng và \(C\) cột. Cho biết vị trí ô chứa bóng, vị trí ô chứa hố cần đánh bóng vào và vị trí của ô có vật cản. Tại mỗi lần chơi, người chơi có thể đánh quả bóng theo một trong bốn hướng (trên, dưới, trái, phải), quả bóng có thể di chuyển không quá \(K\) ô liên tiếp và không thể đi qua ô có vật cản.

Yêu cầu: Hãy tính số lần đánh bóng ít nhất để đưa được bóng vào hố.

Dữ liệu vào từ tệp văn bản GOLF.INP:

• Dòng đầu tiên gồm ba số nguyên dương \(R, C\) và \(K\) \((R \times C \le 10^6; \ K \le 10^6)\);
• \(R\) dòng tiếp theo, mỗi dòng chứa \(C\) kí tự thuộc bốn loại kí tự sau:
  • . là vị trí ô trống;
  • # là vị trí ô có vật cản;
  • S là vị trí của bóng, có duy nhất một kí tự S trong bảng;
  • G là vị trí của hố, có duy nhất một kí tự G trong bảng.

Dữ liệu đảm bảo luôn có cách đưa bóng vào hố.

Kết quả ghi ra tệp văn bản GOLF.OUT:

Gồm một số nguyên duy nhất là số lần đánh bóng ít nhất cần thực hiện.

Ví dụ

Input

2 5 1
S#...
...#G

Output

7

Input

2 5 10
S#...
...#G

Output

5

Ràng buộc

• Có \(20\%\) số test ứng với \(20\%\) số điểm không có kí tự # trong bảng;
• \(20\%\) số test khác ứng với \(20\%\) số điểm có \(R \le 2\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm có \(R, C, K \le 10^2\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm có \(K \ge \max(R, C)\);
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc gì thêm.

Kế hoạch thực hiện công việc của một công ty là một danh sách gồm \(N\) công việc được đánh số thứ tự từ \(1\) đến \(N\), mỗi công việc cho biết thời gian để chuẩn bị và thời gian để thực hiện công việc đó. Tuy nhiên công ty chỉ có một đội ngũ nhân viên làm nhiệm vụ chuẩn bị và một đội ngũ nhân viên làm nhiệm vụ thực hiện công việc. Tại một thời điểm chỉ có một công việc được chuẩn bị và một công việc được thực hiện.

Thực tế khi triển khai, công ty có thêm \(M\) yêu cầu gồm một trong hai loại như sau:

• Thêm một công việc mới: Có thời gian chuẩn bị là \(u\) và thời gian thực hiện là \(v\). Công việc mới được đánh số tiếp theo trong danh sách;
• Loại bỏ công việc có số thứ tự \(k\).

Yêu cầu: Tìm cách sắp xếp tối ưu để \(N\) công việc ban đầu được hoàn thành sớm nhất. Với mỗi yêu cầu, đưa ra thời gian sớm nhất để hoàn thành công việc từ đầu đến thời điểm hoàn thành yêu cầu đó.

Dữ liệu vào từ tệp văn bản SCHEDU.INP:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) \((1 \le N \le 2 \times 10^5; \ 0 \le M \le 2 \times 10^5)\);
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x, y\) \((1 \le x, y \le 10^9)\) mô tả thời gian chuẩn bị và thời gian thực hiện của \(N\) công việc đầu tiên;
• \(M\) dòng tiếp theo mô tả lần lượt các yêu cầu theo định dạng:
  • 1 u v: Mô tả yêu cầu có thêm một công việc mới có thời gian chuẩn bị là \(u\) và thời gian thực hiện là \(v\) \((1 \le u, v \le 10^9)\);
  • 2 k: Mô tả yêu cầu loại bỏ công việc có thứ tự \(k\).

Dữ liệu đảm bảo tính nhất quán và luôn có đáp án. Không có công việc nào bị loại bỏ rồi mà xuất hiện yêu cầu loại bỏ sau đó và đảm bảo lúc nào cũng còn ít nhất một công việc.

Kết quả ghi ra tệp văn bản SCHEDU.OUT:

• Dòng đầu tiên ghi ra thời gian sớm nhất để \(N\) công việc ban đầu được hoàn thành;
• \(M\) dòng tiếp theo, tương ứng với mỗi yêu cầu ghi ra thời gian sớm nhất để hoàn thành các công việc từ đầu đến thời điểm hoàn thành yêu cầu đó.

Ví dụ

Input

2 0
1 3
2 3

Output

7

Input

1 4
4 3
1 3 8
1 5 2
2 1
2 3

Output

7
14
16
13
11

Ràng buộc

• Có \(25\%\) số test ứng với \(25\%\) số điểm có \(1 \le N \le 9; \ M = 0\);
• \(25\%\) số test khác ứng với \(25\%\) số điểm có \(1 \le N \le 20; \ M = 0\);
• \(25\%\) số test khác ứng với \(25\%\) số điểm có \(1 \le N \le 2 \times 10^5; \ M = 0\);
• \(25\%\) số test còn lại ứng với \(25\%\) số điểm không có ràng buộc gì thêm.