Taro đến lễ hội mùa hè tại đền JOI. Dọc đường đến đền có \(N\) gian hàng chợ đêm, được đánh số từ \(1\) đến \(N\) theo thứ tự. Chơi tại gian hàng \(i\) mang lại mức độ vui thích \(A_i\) và mất \(B_i\) đơn vị thời gian.

Lễ hội còn có màn trình diễn pháo hoa. Quả pháo hoa lớn nhất được bắn vào thời điểm \(S\), và Taro muốn xem nó. Cậu lập kế hoạch từ khi đến lễ hội ở thời điểm \(0\) đến khi lễ hội kết thúc ở thời điểm \(T\).

Taro chọn \(k\) gian hàng, với \(1\le k\le N\), không chọn gian hàng nào hai lần. Gọi số hiệu các gian hàng đã chọn theo thứ tự tăng dần là \(y_1,y_2,\ldots,y_k\). Cậu chọn một thời điểm nguyên \(x_{y_i}\) để đến gian hàng \(y_i\), và chơi ở đó từ thời điểm \(x_{y_i}\) đến thời điểm \(x_{y_i}+B_{y_i}\).

Taro phải chơi theo thứ tự số hiệu gian hàng tăng dần và không thể chơi ở hai gian hàng cùng lúc. Có thể bỏ qua thời gian di chuyển giữa các gian hàng. Sau thời điểm \(T\), cậu không được chơi nữa. Trong lúc chơi, cậu không thể xem pháo hoa; tuy nhiên, nếu thời điểm \(S\) đúng bằng lúc bắt đầu hoặc kết thúc chơi tại một gian hàng thì cậu vẫn xem được pháo hoa.

Như vậy, một kế hoạch hợp lệ phải thỏa mãn:

• \(y_1<y_2<\cdots<y_k\).
• Các thời điểm \(x_{y_1},x_{y_2},\ldots,x_{y_k}\) đều là số nguyên.
• Các khoảng thời gian chơi nằm trong thời gian lễ hội và không chồng lấn:

• Không tồn tại chỉ số \(i\) sao cho \(x_{y_i} < S < x_{y_i}+B_{y_i}\).

Gọi \(M\) là tổng mức độ vui thích của các gian hàng được chọn:

Yêu cầu

Cho thông tin \(N\) gian hàng cùng các thời điểm \(S,T\), hãy tìm giá trị lớn nhất của \(M\) trong một kế hoạch hợp lệ.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa ba số nguyên \(N,T,S\), lần lượt là số gian hàng, thời điểm kết thúc lễ hội và thời điểm bắn quả pháo hoa lớn nhất.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\) mô tả gian hàng \(i\).

Các số trên cùng một dòng được phân cách bởi dấu cách. Bảo đảm có ít nhất một kế hoạch hợp lệ.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa giá trị lớn nhất của \(M\).

Ràng buộc

• \(1\le N\le3000\).
• \(1\le T\le3000\).
• \(0\le S\le T\).
• \(0\le A_i\le100\,000\) với mọi \(1\le i\le N\).
• \(1\le B_i\le3000\) với mọi \(1\le i\le N\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

• \(10\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le20\).
• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(S=0\).

Tổng cộng \(30\%\) số điểm dành cho các dữ liệu thỏa mãn ít nhất một trong hai điều kiện \(N\le20\) hoặc \(S=0\). Không có dữ liệu chấm nào đồng thời thỏa mãn cả hai điều kiện này.

Ví dụ

5 20 14
8 9
2 4
7 13
6 3
5 8

16