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^5, S ≤ 10^7)~.

• ~n~ dòng tiếp theo, mỗi dòng gồm:

  • 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, mỗi dòng gồm tên và lương thực nhận (sau thuế) của nhân viên thỏa yêu cầu.

• Lương thực nhận đượ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