EIU Programming Practices and Exams

Cuối năm công ty ABC muốn tuyển nhân viên với lương được tính theo sản phẩm làm ra. Nhân viên phải đóng thuế thu nhập cá nhân theo quy định nhà nước như sau:

• Số tiền tính thuế là khoản còn lại sau khi giảm trừ cá nhân (9 triệu đồng) và các giảm trừ khác.
• Bậc 1: 0 - 5 triệu đồng/tháng: 5%;
• Bậc 2: Trên 5 – 10 triệu đồng/tháng: 10%;
• Bậc 3: Trên 10 – 18 triệu đồng: 15%;
• Bậc 4: Trên 18 - 32 triệu đồng/tháng: 20%;
• Bậc 5: Trên 32 – 52 triệu đồng/tháng: 25%;
• Bậc 6: Trên 52 – 80 triệu đồng/tháng: 30%;
• Bậc 7: Trên 80 triệu đồng/tháng: 35%;

Hãy xuất danh sách không quá k nhân viên được hưởng lương cao nhất sau khi trừ thuế theo ưu tiên thứ tự lương thực nhận, tên nhân viên. Nếu 2 nhân viên cùng mức lương thì hoặc cùng được xuất ra hoặc cùng không được xuất ra.

Input

Dòng đầu tiên là số nhân viên n, số nguyên k, lương mỗi sản phẩm S (0 ≤ k ≤ n ≤ 10⁵, S ≤ 10⁷ ).

N dòng tiếp theo, mỗi dòng là tên nhân viên (gồm các kí tự in thường), số sản phẩm làm được, số tiền được giảm trừ khác

Output

Không quá k dòng gồm các nhân viên thỏa yêu cầu gồm tên và lượng thực nhận (sau thuế)

Lưu ý. Tiền lương thực nhận khi xuất ra được làm tròn tới hàng đơn vị.

Example

Input:
5 3 100000
A 105 3600000
B 105 7200000
C 100 0
E 112 0
E 200 3600000

Output:
E 19510000
E 11090000