Trong thị trấn của bạn có một hiệu sách cũ lâu đời mang tên JOI mà bạn thường xuyên ghé thăm. Mỗi cuốn sách có một giá cơ bản xác định, và hiệu sách JOI sẽ mua lại cuốn sách với giá đó.

Hiệu sách phân loại sách thành \(10\) thể loại, chẳng hạn như tiểu thuyết, truyện tranh và tạp chí. Các thể loại được đánh số từ \(1\) đến \(10\). Hiệu sách có dịch vụ mua lại với giá cao hơn nếu bạn bán cùng lúc nhiều cuốn sách thuộc cùng một thể loại. Cụ thể, nếu bán cùng lúc \(T\) cuốn sách thuộc một thể loại, giá mua lại của mỗi cuốn trong số đó sẽ cao hơn giá cơ bản của nó \(T-1\) yên. Ví dụ, nếu bán cùng lúc ba cuốn sách cùng thể loại có giá cơ bản lần lượt là \(100\), \(120\), \(150\) yên, giá mua lại tương ứng sẽ là \(102\), \(122\), \(152\) yên.

Vì lý do cá nhân, bạn đột ngột phải chuyển nhà. Bạn có \(N\) cuốn sách, nhưng khó có thể mang tất cả đến nơi ở mới, nên quyết định bán đúng \(K\) cuốn trong số đó cho hiệu sách JOI.

Yêu cầu

Cho giá cơ bản và số hiệu thể loại của từng cuốn sách, hãy viết chương trình tính tổng số tiền lớn nhất có thể nhận được khi bán sách.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(N,K\), cách nhau bởi dấu cách, cho biết bạn có \(N\) cuốn sách và sẽ bán \(K\) cuốn.
• \(N\) dòng tiếp theo mô tả các cuốn sách. Dòng \(i+1\) (\(1\le i\le N\)) chứa hai số nguyên \(C_i,G_i\), cách nhau bởi dấu cách, lần lượt là giá cơ bản và số hiệu thể loại của cuốn sách thứ \(i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: tổng số tiền lớn nhất có thể nhận được khi bán sách.

Ràng buộc

• \(2\le N\le2000\).
• \(1\le K<N\).
• \(1\le C_i\le100000=10^5\) với mọi \(1\le i\le N\).
• \(1\le G_i\le10\) với mọi \(1\le i\le N\).
• Giới hạn thời gian: \(1\) giây. Giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm. Các điều kiện điểm thành phần dưới đây có chồng lấp:

• Các bộ dữ liệu chiếm \(20\%\) tổng số điểm thỏa mãn \(N\le20\).
• Các bộ dữ liệu chiếm \(20\%\) tổng số điểm thỏa mãn \(G_i\in\{1,2\}\) với mọi \(1\le i\le N\).
• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm đồng thời thỏa mãn \(N\le20\) và \(G_i\in\{1,2\}\) với mọi \(1\le i\le N\).
• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn ít nhất một trong hai điều kiện: \(N\le20\); hoặc \(G_i\in\{1,2\}\) với mọi \(1\le i\le N\).

Ví dụ

7 4
14 1
13 2
12 3
14 2
8 2
16 3
11 2

60