Trò chơi hỏi đáp

Bạn đang thiết kế một trò chơi hỏi đáp cho $n$ nhiệm vụ. Nhiệm vụ thứ $i$ có độ thú vị $q_i$ và cần $t_i$ phút để hoàn thành.

Trò chơi được tổ chức dưới dạng một cây nhị phân: mỗi nút trong chứa một câu hỏi, mỗi lá chứa một nhiệm vụ. Người chơi bắt đầu từ gốc; tại mỗi câu hỏi họ trả lời "có" hoặc "không" và đi theo một trong hai nhánh, cho tới khi tới một lá và nhận nhiệm vụ ở đó. Trả lời mỗi câu hỏi tốn đúng $1$ phút.

Nếu một nhiệm vụ nằm ở độ sâu $d$ (tức là để tới được nó người chơi phải trả lời $d$ câu hỏi), thì tổng thời gian người chơi bỏ ra khi chọn nhiệm vụ đó là $d+t_i$ phút. Cây có thể chỉ gồm đúng một nhiệm vụ và không có câu hỏi nào (khi đó $d=0$).

Mỗi nhiệm vụ được dùng nhiều nhất một lần (các cách trả lời khác nhau phải dẫn tới các lá khác nhau). Bạn được chọn một tập con các nhiệm vụ và sắp xếp chúng thành cây sao cho với mọi cách trả lời, tổng thời gian không vượt quá $T$ phút, tức là mọi nhiệm vụ được chọn ở độ sâu $d$ đều thỏa $d+t_i\le T$.

Hãy tìm tổng độ thú vị lớn nhất của các nhiệm vụ có thể đưa vào cây.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $T$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $t_i$ và $q_i$.

Dữ liệu ra

• In ra một số nguyên duy nhất: tổng độ thú vị lớn nhất có thể đạt được.

Ràng buộc

• $1\le n\le 1000$
• $1\le T\le 100$
• $1\le t_i\le T$
• $1\le q_i\le 1000$

Ví dụ