Năm 2020, Công ty cổ phần liên doanh ô tô Hyundai Việt Nam đã xuất khẩu 5 lần, mỗi lần xuất đi với \(n\) chiếc xe ô tô bằng cách cho tàu thủy mang biển kiểm soát VN6789 vận chuyển qua đường biển.

Với mỗi chiếc ô tô thứ \(i\ (1 \le i \le n)\), có trọng lượng là \(K_i\ (1 \le K_i \le 10^9)\) và giá trị \(U_i\ (1 \le U_i \le 10^9)\). Công ty mong muốn xuất được nhiều xe nhưng tàu chỉ vận chuyển khối lượng hàng nằm trong quy định cho phép \(Q\ (1 \le Q \le 1000)\). Vì thế, công ty đã thử chọn phương án cho mỗi lần xuất khẩu là mỗi loại xe chỉ lấy đi một chiếc sao cho những chiếc xe đã xuất đi có tổng giá trị lớn nhất.

Kể từ những lần xuất khẩu của năm đó, lợi nhuận của công ty tăng lên vượt bậc. Dự kiến đến năm 2025, công ty cổ phần liên doanh ô tô Hyundai Việt Nam sẽ xuất khẩu ô tô thêm 5 lần nữa. Trong năm này, Giám đốc công ty đưa ra yêu cầu cho bộ phận kinh doanh phải tiếp tục hợp đồng với tàu chở hàng VN6789 để mỗi lần xuất khẩu, các xe sẽ chọn đi sao cho tổng giá trị năm 2025 phải cao hơn tổng giá trị các chiếc xe mỗi lần xuất đi năm 2020. Đồng thời, tính giá trị hao hụt qua các lần xuất khẩu giữa năm 2020 và 2025 là bao nhiêu? Biết rằng, phương án được chọn cho các chuyến đi năm 2025 là mỗi loại xe có thể chọn số lượng nhiều.

Yêu cầu: Để đáp ứng mong đợi của ban giám đốc, theo em bộ phận kinh phải làm thế nào để đưa ra giá trị hao hụt qua những lần xuất khẩu của năm 2020 so với 2025.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(Q\) (các giá trị cách nhau một khoảng trắng)
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(K_i\) và \(U_i\) (các giá trị cách nhau một khoảng trắng).

Output

• Ghi ra tệp văn bản BOATCAR.OUT gồm 3 dòng:
  • Dòng thứ nhất chứa tổng giá trị cho mỗi lần xuất khẩu xe đi trong năm 2020.
  • Dòng thứ hai chứa tổng giá trị cho mỗi lần xuất khẩu xe đi trong năm 2025.
  • Dòng thứ ba chứa giá trị hao hụt các xe đã xuất khẩu trong năm 2020 so với năm 2025.

Example

5 12
1 1
2 2
10 4
4 18
2 3 

24 
54 
150

Scoring

• Có \(40\%\) test tương ứng \(40\%\) số điểm của bài với \(n \le 30; 1 \le U_i \le 10^2; 1 \le K_i \le 10^2\)
• Có \(40\%\) test tương ứng \(40\%\) số điểm của bài với \(n < 10^2; 10^2 < U_i \le 10^6; 10^2 < K_i \le 10^6\)
• Có \(20\%\) test tương ứng \(20\%\) số điểm của bài với \(n \le 10^3; 10^6 < U_i \le 10^9; 10^6 \le K_i \le 10^9\)