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.