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.

Một trò chơi có luật chơi như sau: Người chơi ban đầu có ~W~ năng lượng và trò chơi có ~N~ màn chơi, màn chơi thứ ~i~ có các thông tin như sau:

• Năng lượng của màn chơi là ~m_i~ - mỗi khi chơi màn này, năng lượng sẽ giảm đi ~m_i~;
• Điểm kinh nghiệm của màn chơi là ~e_i~ - người chơi thu được ~e_i~ điểm kinh nghiệm;
• Trừ điểm kinh nghiệm khi chơi lại là ~s_i~ - mỗi khi chơi lại màn này, số điểm kinh nghiệm nhận được sẽ bị giảm đi ~s_i \times (k - 1)~ (với ~k~ là số lần chơi màn này). Tức là, số điểm kinh nghiệm thu được khi chơi màn chơi thứ ~i~ tại lần thứ ~k~ là ~e_i - s_i \times (k - 1)~;
• Có thể chọn các màn chơi không cần theo thứ tự. Năng lượng của người chơi phải lớn hơn hoặc bằng năng lượng của màn chơi thì mới chơi được màn chơi đó.

Yêu cầu: Đưa ra tổng điểm kinh nghiệm lớn nhất có thể thu được khi chơi trò chơi trên.

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

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~W~ ~(N \le 2 \times 10^5;~ ~W \le 3000)~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~m_i, e_i, s_i~ ~(1 \le i \le N; \ m_i \le 3000; \ s_i \le e_i \le 10^5)~.

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

Gồm một số nguyên duy nhất là tổng điểm kinh nghiệm lớn nhất thu được thoả mãn yêu cầu đề bài.

Ví dụ

Input

2 10
2 6 2
5 5 5

Output

15

Giải thích

• Lần ~1~: Chơi màn chơi thứ ~1~: Mất ~2~ năng lượng, điểm kinh nghiệm thu được là ~6~;
• Lần ~2~: Chơi màn chơi thứ ~2~: Mất ~5~ năng lượng, điểm kinh nghiệm thu được là ~5~;
• Lần ~3~: Chơi lại màn chơi thứ ~1~: Mất ~2~ năng lượng, điểm kinh nghiệm thu được là ~4~;

~\Rightarrow~ Vậy mất tổng cộng ~9~ năng lượng và tổng điểm kinh nghiệm thu được là ~15~.

Input

2 8
3 4 2
2 3 1

Output

9

Giải thích

• Lần ~1~: Chơi màn chơi thứ ~1~: Mất ~3~ năng lượng, điểm kinh nghiệm thu được là ~4~;
• Lần ~2~: Chơi lại màn chơi thứ ~1~: Mất ~3~ năng lượng, điểm kinh nghiệm thu được là ~2~;
• Lần ~3~: Chơi màn chơi thứ ~2~: Mất ~2~ năng lượng, điểm kinh nghiệm thu được là ~3~;

~\Rightarrow~ Vậy mất tổng cộng ~8~ năng lượng và tổng điểm kinh nghiệm thu được là ~9~.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm có ~N \le 2; \ W \le 20~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N, W \le 300~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N \le 1000~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có năng lượng của màn chơi là như nhau;
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm không có ràng buộc gì thêm.

Cho dãy số ~N~ phần tử được đánh vị trí từ ~0~ đến ~N-1~ và một số ~k~. Ta thực hiện các bước xoá phần tử của dãy số như sau: Xét các phần tử ở các vị trí ~0, \ k, \ 2 \times k,~ ~3 \times k, \dots~, tìm phần tử đầu tiên có giá trị lớn nhất và xoá phần tử đó đi, sau đó các phần tử còn lại sẽ được dồn lại. Thực hiện các bước xoá như trên đến khi dãy số không còn phần tử nào.

Yêu cầu: Hãy đưa ra giá trị của các phần tử bị xoá tại mỗi bước.

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

• Dòng đầu tiên chứa hai số nguyên ~N, k~ ~(2 \le k \le N \le 10^5)~;
• Dòng thứ hai chứa ~N~ số nguyên ~a_i~ ~(0 \le i \le N-1; \ 1 \le a_i \le N)~.

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

Gồm ~N~ dòng, mỗi dòng là giá trị của phần tử bị xoá tại mỗi bước.

Ví dụ

Input

10 3
2 3 1 9 10 4 5 6 1 5

Output

9
10
4
5
6
2
5
3
1
1

Ràng buộc

• Có ~20\%~ số test ứng với ~20\%~ số điểm có ~N \le 10^3~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~k = 2~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~k \le 10~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~100 \le k \le N~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.

Trên trục ~Ox~, cho ~M~ điểm có toạ độ nguyên dương được đánh số từ ~1~ đến ~M~: ~a_1, a_2, \dots, a_M~ và ~N~ đoạn thẳng ~[l_i, r_i]~ được đánh số từ ~1~ đến ~N~ (không có đoạn thẳng nào nằm trong nhau).

Xét lần lượt các đoạn thẳng, với đoạn thẳng thứ ~i~ là đoạn ~[l_i, r_i]~ có hai lựa chọn như sau:

• Lựa chọn ~1~: Chọn ra một điểm từ tập các điểm đã cho (điểm này chưa được chọn trước đó), sao cho điểm đó không nằm trong đoạn ~[l_i, r_i]~;
• Lựa chọn ~2~: Bỏ qua đoạn thẳng này.

Yêu cầu: Chỉ được sử dụng lựa chọn ~2~ nhiều nhất ~K~ lần, tính số lượng lựa chọn ~1~ được sử dụng nhiều nhất. Chú ý, nếu sử dụng hết ~K~ lần lựa chọn ~2~ và không chọn được điểm thoả mãn lựa chọn ~1~ thì kết thúc việc xét các đoạn thẳng.

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

• Dòng đầu tiên gồm ba số nguyên ~M, N, K~ ~(0 \le K \le N \le M \le 10^6)~ là số lượng điểm, số lượng đoạn thẳng và số lần tối đa sử dụng lựa chọn ~2~;
• Dòng thứ hai chưa ~M~ số nguyên dương ~a_1, a_2, \dots, a_M~ ~(1 \le i \le M; \ a_i \le 10^9)~;
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~l_i, r_i~ ~(1 \le i \le N; \ l_i \le r_i \le 10^9)~ mô tả đoạn thẳng thứ ~i~.

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

Gồm một số nguyên duy nhất là số lần lựa chọn ~1~ được sử dụng nhiều nhất.

Ví dụ

Input

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

Output

2

Giải thích

• Đoạn thẳng ~1~: Sử dụng lựa chọn ~2~;
• Đoạn thẳng ~2~: Sử dụng lựa chọn ~1~, chọn điểm thứ ~1~ có toạ độ là ~1~ (không nằm trong đoạn ~[2, 5]~);
• Đoạn thẳng ~3~: Sử dụng lựa chọn ~1~, chọn điểm thứ ~4~ có toạ độ là ~2~ (không nằm trong đoạn ~[3, 6]~).

~\Rightarrow~ ~2~ lần sử dụng lựa chọn ~1~.

Input

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

Output

3

Giải thích

• Đoạn thẳng ~1~: Sử dụng lựa chọn ~1~, chọn điểm thứ ~2~ có toạ độ là ~7~;
• Đoạn thẳng ~2~: Sử dụng lựa chọn ~1~, chọn điểm thứ ~1~ có toạ độ là ~4~;
• Đoạn thẳng ~3~: Sử dụng lựa chọn ~1~, chọn điểm thứ ~4~ có toạ độ là ~7~;
• Đoạn thẳng ~4~: Không chọn được điểm thoả mãn, kết thúc.

~\Rightarrow~ ~3~ lần sử dụng lựa chọn ~1~.

Ràng buộc

• Có ~10\%~ số test ứng với ~10\%~ số điểm có ~M \le 10~;
• ~10\%~ số test khác ứng với ~10\%~ số điểm có ~M \le 20~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~M \le 10^3~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~M \le 10^5;~ ~K=0~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~M \le 10^5~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.