Sau khi xuất sắc giành ''cú ăn ba lịch sử'' trong kỳ thi học sinh giỏi quốc gia, Hiếu quyết tâm đăng ký tham dự Giải đấu Lập trình đối kháng tranh Cúp NTHA. Tại cuộc thi này, Hiếu phải vượt qua \(n\) coder siêu hạng khác để chinh phục được NTHA. Các đối thủ của Hiếu lần lượt được đánh số từ \(1\) đến \(n\). Thể thức của giải đấu như sau: Giải đấu diễn ra trong một ngày duy nhất với rất nhiều trận đấu hấp dẫn. Mỗi trận đấu là cuộc so tài giữa hai thí sinh theo hình thức đối kháng, kết quả chỉ có thắng và thua. Thí sinh nào dành được càng nhiều chiến thắng, thứ hạng sẽ càng cao và giải thưởng sẽ càng lớn.

Theo quy định của trưởng ban tổ chức - mrs. NTHA, các thí sinh tham dự giải cần có mặt lúc 8 giờ sáng để làm lễ khai mạc trước khi bước vào cuộc so tài. Tuy nhiên, với bản tính hay chậm của mình, Hiếu chỉ thức giấc khi đồng hồ đã điểm... 12 giờ trưa. Và hẳn nhiên, khi Hiếu tới nơi, tất cả các trận đấu giữa các đối thủ của Hiếu đều đã kết thúc, và cả \(n\) đối thủ đều đã phải chờ Hiếu dài cổ. Thế nhưng, do có mối quan hệ đặc biệt với mrs. NTHA, Hiếu vẫn được sắp xếp tham dự giải đấu.

Sau khi tất cả các trận đấu giữa các đối thủ của của Hiếu với nhau khép lại, số điểm của \(n\) đối thủ lần lượt là \(p_1, p_2, \ldots, p_n\). Do chưa đấu trận nào, Hiếu hiện tại có \(0\) điểm. Giải đấu chỉ còn lại \(n\) trận đấu nữa, là các trận của Hiếu với \(n\) đối thủ. Như vậy, mỗi đối thủ của Hiếu hiện còn chính xác một trận chưa đấu (là trận đấu với Hiếu) và Hiếu có chính xác \(n\) trận để đấu (mỗi trận với một đối thủ khác nhau). Trong \(n\) trận đấu này, mỗi trận đấu kết thúc với phần thắng thuộc về một trong hai thí sinh, thí sinh thắng được thêm \(1\) điểm còn người thua cuộc không bị trừ điểm. Thứ hạng chung cuộc của Hiếu trong giải đấu được xác định như sau:

• Thí sinh nào có điểm cao hơn Hiếu chắc chắn xếp trên Hiếu.
• Thí sinh nào có điểm thấp hơn Hiếu chắc chắn xếp dưới Hiếu.
• Nếu một đối thủ bằng điểm với Hiếu, Hiếu sẽ xếp trên nếu thắng trong trận đấu trực tiếp với đối thủ này, và xếp dưới trong trường hợp để thua.
• Thứ hạng của Hiếu trong giải đấu được tính bằng (\(1 +\) số đối thủ xếp trên Hiếu).

Trước giải đấu, Hiếu đã tìm hiểu rất kỹ về các đối thủ của mình. Hiếu cho rằng mình có thể đánh bại bất kỳ ai, nhưng sẽ mất lượng năng lược là \(e_i\) để dành chiến thắng trong trận đấu với đối thủ thứ \(i\). Tất nhiên, Hiếu sẽ không mất năng lượng nếu cố tình để thua trong trận đấu nào đó. Sau ''cú ăn ba lịch sử'', Hiếu cho rằng mục tiêu khi tham dự giải không phải là để chinh phục NTHA mà là đạt được thứ hạng \(k\) hoặc tốt hơn. Các bạn hãy giúp Hiếu tìm ra chiến thuật để hoàn thành mục tiêu mà tốn ít năng lượng nhất nhé.

Input

Dòng đầu tiên chứa số nguyên \(\theta\) \((1 \leq \theta \leq 10^7)\) là số bộ dữ liệu. Tiếp theo là các bộ dữ liệu lần lượt được mô tả theo khuôn dạng sau:

• Dòng đầu tiên là một dòng trống.
• Dòng thứ hai chứa hai số nguyên \(n\) và \(k\) \((1 \leq n \leq 262144, 1 \leq k \leq n + 1)\) lần lượt là số đối thủ của Hiếu trong giải, và mục tiêu về thứ hạng chung cuộc của Hiếu.
• Trong \(n\) dòng còn lại, dòng thứ \(i\) chứa hai số nguyên \(p_i\) và \(e_i\) \((0 \leq p_i, e_i \leq 10^9)\) lần lượt là số điểm đối thủ thứ \(i\) có trước khi các trận đấu của Hiếu diễn ra, và năng lượng Hiếu cần để chiến thắng đối thủ này.

Dữ liệu vào đảm bảo tổng \(n\) trong các bộ dữ liệu của một file input không quá \(2097152\).

Output

• Với mỗi bộ dữ liệu, in ra một số nguyên là năng lượng tối thiểu Hiếu cần để đạt được thứ hạng \(k\) hoặc tốt hơn; hoặc \(-1\) nếu như Hiếu không thể hoàn thành mục tiêu này ngay cả khi đã thắng tất cả các đối thủ.

Example

4

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

3 3
4 0
4 0
4 0

2 3
22 7
19 97

5 1
5 2
5 4
5 8
5 16
5 32

3
-1
0
62