Nhờ sự giúp đỡ của bạn, Hỏa tinh chỉ chịu tổn thất tối thiểu. Tuy nhiên, Hạo quá lười để tái thiết lại hành tinh, nên anh ta đã chế tạo một con tàu vũ trụ và bay tới hành tinh xa xôi - Trái Đất.

Giữa đường, Hạo bỗng nhận ra một vấn đề rất nghiêm trọng: {anh ta đang đói bụng}!

May mắn thay, Hạo vẫn còn biết nấu ăn, và cũng có đem theo một ít nguyên liệu. Nhưng công thức tính "mức độ ngon" của món ăn lại khá kỳ quặc, nên anh ta đành nhờ đến bạn để giúp tối ưu thực đơn cho chuyến bay còn lại.

Có tất cả \(n\) nguyên liệu. Mỗi nguyên liệu \(i\) có ba thuộc tính:

• \(a_i\): độ ngon cơ bản của món ăn nếu làm xong ngay lập tức,
• \(b_i\): độ giảm độ ngon mỗi đơn vị thời gian trôi qua,
• \(c_i\): thời gian cần để chế biến nguyên liệu này.

Giả sử món ăn thứ \(i\) được hoàn thành vào thời điểm \(t\), thì độ ngon của nó được tính bằng: \[ a_i - t \times b_i \] Tổng thời gian nấu các món không được vượt quá \(T\) (thời gian còn lại cho đến khi đến Trái Đất).

Yêu cầu

• Chọn một số món và thứ tự chế biến sao cho tổng độ ngon là lớn nhất.

Dữ liệu vào

• Dòng đầu: hai số nguyên \(T\) và \(n\) - thời gian còn lại và số nguyên liệu.
• Dòng thứ hai: \(n\) số nguyên \(a_1, a_2, \dots, a_n\).
• Dòng thứ ba: \(n\) số nguyên \(b_1, b_2, \dots, b_n\).
• Dòng thứ tư: \(n\) số nguyên \(c_1, c_2, \dots, c_n\).

Dữ liệu ra

• Một số nguyên - tổng độ ngon lớn nhất có thể đạt được trong thời gian \(T\).

Giới hạn dữ liệu

• Với \(40\%\) dữ liệu: \(1 \le n \le 10\)
• Với \(100\%\) dữ liệu: \(1 \le n \le 50\)
• Tất cả giá trị \(a_i, b_i, c_i \le 10^5\)

Input 1

74 1
502
2
47

Output 1

408

Giải thích ví dụ

• Nếu nấu món duy nhất vào thời điểm \(t=47\) (sau khi nấu xong): \[ \text{Độ ngon} = 502 - 47 \times 2 = 408 \]