Có ~N~ đảo được đánh số từ ~1~ đến ~N~. đảo ~i~ có độ cao ~h_i~, số điểm ~c_i~ và hai tham số ~a_i, b_i~.

Bạn được chọn một đảo bất kỳ làm đảo bắt đầu. Khi đến một đảo, bạn nhận số điểm của đảo đó. Từ đảo ~i~, bạn có thể nhảy tới đảo ~j~ nếu đồng thời thỏa mãn:

• ~i+a_i \le j \le i+b_i~.

• ~D_1 \le h_j-h_i \le D_2~.

Các đảo nằm ngoài đoạn ~[1,N]~ được bỏ qua. Bạn có thể dừng lại tại bất kỳ thời điểm nào.

Hãy tìm tổng số điểm lớn nhất có thể nhận được.

Input

• Dòng đầu tiên chứa ba số nguyên ~N, D_1, D_2~ ~(1 \le N \le 5 \cdot 10^5, 0 \le D_1 \le D_2 \le 10^9)~.

• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa bốn số nguyên ~h_i, c_i, a_i, b_i~ ~(0 \le h_i,c_i \le 10^9, 1 \le a_i \le b_i \le N)~.

Output

In ra một số nguyên duy nhất là tổng số điểm lớn nhất có thể nhận được.

Scoring

Sample Input 1

6 2 5
1 4 1 3
3 7 2 3
6 5 1 2
4 6 1 2
8 9 1 1
10 3 1 1

Sample Output 1

23

Notes

Một cách đi tối ưu là chọn đảo ~1~ làm điểm bắt đầu, sau đó lần lượt nhảy qua các đảo ~2,5,6~. Các bước nhảy đều thỏa mãn cả giới hạn chỉ số và giới hạn chênh lệch độ cao. Tổng điểm nhận được là ~4+7+9+3=23~.