Cho ~n~ sản phẩm, sản phẩm thứ ~i~ ~(1 \le i \le n)~ được bán với giá ~w_i~ trong vòng ~d_i~ giờ kể từ lúc mở cửa. Một tập các sản phẩm được gọi là "mua được" nếu mọi sản phẩm trong tập đều có thể mua nhưng mỗi giờ chỉ được mua đúng một sản phẩm. Việc mua sản phẩm được thực hiện bắt đầu từ giờ ~1~.

Xét hai tập mua được ~\text{P}~ và ~\text{Q}~: ~\text{P}~ được gọi là tốt hơn ~\text{Q}~ nếu số lượng sản phẩm trong ~\text{P}~ nhiều hơn ~\text{Q}~ hoặc hai tập có số sản phẩm bằng nhau nhưng tổng giá của ~\text{P}~ nhỏ hơn ~\text{Q}~.

Trong tất cả tập sản phẩm mua được có thể tạo thành, hãy xác định số sản phẩm và giá của ~k~ tập sản phẩm mua được tốt nhất.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~(1 \le n,k \le 2000)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~w_i~ và ~d_i~ ~(1 \le w_i \le 10^9; \; 1 \le d_i \le n)~.

Output

• In ra ~k~ dòng, dòng thứ ~j~ ~(1 \le j \le k)~ là số sản phẩm và tổng giá của tập sản phẩm mua được tốt thứ ~j~.

Samples

Sample Input 1

3 1
1 1
1 1
1 3

Sample Output 1

2 2

Sample Input 2

4 3
1 1
10 1
2 3
10 3

Sample Output 2

3 13
3 22
2 3

Sample Input 3

2 4
1 1
2 2

Sample Output 3

2 3
1 1
1 2
0 0

Scoring

• Subtask ~1~ với ~15\%~ số điểm: ~k=1; \; w_1=w_2=...=w_n~
• Subtask ~2~ với ~15\%~ số điểm: ~k=1~
• Subtask ~3~ với ~15\%~ số điểm: ~k=2~
• Subtask ~4~ với ~15\%~ số điểm: ~n \le 20~
• Subtask ~5~ với ~20\%~ số điểm: ~n,k \le 100~
• Subtask ~6~ với ~20\%~ số điểm: Không còn ràng buộc gì thêm

Clarification

Trong ví dụ thứ hai, hai sản phẩm ~1~ và ~2~ chỉ có thể mua ở giờ ~1~, vì vậy không thể nằm trong cùng một tập sản phẩm mua được. Các tập sản phẩm tốt nhất, tốt thứ ~2~ và tốt thứ ~3~ lần lượt là ~\{1,3,4\}~, ~\{2,3,4\}~ và ~\{1,3\}~.