Tối đa hóa median lương

Bạn quản lý một công ty có $n$ nhân viên (với $n$ là số lẻ). Bạn có $s$ đồng để chi trả lương, và nhân viên thứ $i$ phải được trả một mức lương nguyên nằm trong đoạn $[l_i,r_i]$.

Hãy phân phối lương sao cho median (số ở giữa) của dãy lương là lớn nhất có thể.

Median của một dãy gồm số lẻ phần tử là phần tử ở vị trí giữa sau khi sắp xếp tăng dần. Ví dụ:

• Median của $[5,1,10,17,6]$ là $6$.
• Median của $[1,2,1]$ là $1$.

Bạn không bắt buộc phải tiêu hết $s$ đồng. Tổng số $l_i$ luôn không vượt quá $s$ (luôn đủ tiền để trả mức lương tối thiểu cho mọi người).

Có $t$ truy vấn độc lập, hãy in ra median lớn nhất có thể đạt được cho mỗi truy vấn.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số truy vấn.
• Mỗi truy vấn:
  • Dòng đầu chứa hai số nguyên $n$ và $s$.
  • $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_i$ và $r_i$.

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên duy nhất — median lương lớn nhất có thể.

Ràng buộc

• $1\le t\le 2·{10}^5$
• $1\le n<2·{10}^5$, $n$ lẻ
• $1\le s\le 2·{10}^{14}$
• $1\le l_i\le r_i\le {10}^9$
• Tổng $n$ trên toàn bộ truy vấn không vượt quá $2·{10}^5$.
• ${\sum }_{i=1}^n{l}_i\le s$ trong mỗi truy vấn.

Ví dụ