Là một fan của game MMORPG, ATM thực sự rất phấn khích khi World of Warcraft Classic được ra mắt. Anh ấy bắt đầu chơi từ ngày đầu tiên và bây giờ chỉ còn hai cấp độ để hoàn thành trò chơi. Tất nhiên, anh ấy không có nhiều thời gian như trước đây khi trò chơi mới xuất hiện, vì vậy anh ấy thực sự muốn hoàn thành hai cấp độ này càng nhanh càng tốt.

Để vượt qua cấp độ đầu tiên, ATM cần có kinh nghiệm là \(s_1\). Chỉ sau khi đạt được nó, anh ta mới có thể chuyển sang cấp độ thứ hai, trong đó anh ta cần nhận được kinh nghiệm thêm là \(s_2\) để hoàn thành mục tiêu.

ATM có danh sách \(n\) nhiệm vụ. Anh ta biết rằng anh ta có thể hoàn thành hai cấp độ với những nhiệm vụ này. Để vượt qua nhiệm vụ thứ \(i\), ATM cần \(t_i\) phút. Do đó, anh ta sẽ nhận được \(x_i\) kinh nghiệm cho nhiệm vụ này.

Khi ATM hoàn thành nhiệm vụ đưa anh ta lên cấp độ tiếp theo, phần kinh nghiệm thừa sẽ được trừ vào kinh nghiệm yêu cầu của cấp độ tiếp theo. Khi anh ta lên cấp, tất cả các nhiệm vụ còn lại sẽ cung cấp ít kinh nghiệm hơn, nhưng chúng cũng sẽ yêu cầu ít thời gian hơn.

Lưu ý rằng nếu ATM hoàn thành một nhiệm vụ, anh ấy sẽ không thể lặp lại nhiệm vụ này nữa (ngay cả ở một cấp độ khác).

Với danh sách các nhiệm vụ, hãy giúp ATM chọn thứ tự mà anh ấy sẽ thực hiện các nhiệm vụ để hoàn thành hai cấp độ cuối cùng nhanh nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên \(n, s_1, s_2\) (\(1\le n, s_1, s_2\le 500\)).
• Dòng thứ \(i\) trong \(n\) tiếp theo chứa 4 số nguyên \(x_i, t_i, y_i, r_i\) (\(1\le y_i \le x_i\le 500, 1\le r_i\le t_i\le 10^9\)) với \(x_i, t_i\) là kinh nghiệm nhận được và thời gian cần để hoàn thành nhiệm vụ \(i\) ở cấp độ thứ nhất, \(y_i, r_i\) là kinh nghiệm nhận được và thời gian hoàn thành ở cấp độ thứ hai.

Output

• Ghi thời gian sớm nhất để hoàn thành 2 cấp độ, nếu không thể thì ghi ra -1.

Example

2 100 100
100 100 10 10
101 11 100 10 

110

4 20 20
40 1000 20 20
6 6 5 5
10 10 1 1
10 10 1 1 

40

2 20 5
10 10 5 5
10 10 5 5 

-1