Để góp phần vào mục tiêu phát triển giáo dục, Ngân hàng X quyết định khởi động hạng mục cho vay không lãi dành cho những sinh viên có hoàn cảnh khó khăn. Sau khi quyết sách được công bố, ngân hàng nhận được \(m\) đơn đăng ký vay vốn, các sinh viên đăng ký vay được đánh số từ 1 đến \(m\), nhu cầu vay của sinh viên \(i\) là \(t_{i}\) đồng. Ngân hàng đã đưa ra phương án:

• Quyết định cho sinh viên vay với tổng số tiền không vượt quá \(n\)

• Số lượng sinh viên được vay nhiều nhất có thể và vẫn đảm bảo nếu sinh viên \(i\) được cho vay thì phải được nhận \(t_{i}\) đồng

• Số tiền người vay ít nhất (trong tất cả những người được chọn) là lớn nhất

• Các mục tiêu được ưu tiên theo đúng thứ tự đưa ra

Em hãy lập trình giúp ngân hàng tìm ra cách cho vay thỏa mãn phương án đưa ra ứng với mỗi số tiền giả định cho vay không vượt quá \(n\).

Dữ liệu vào:

• Dòng 1: Chứa số \(m\) và \(q\)

• Dòng 2: Chứa \(m\) số nguyên dương \(t_{1},t_{2},t_{3},\ldots,t_{m}\ \left( t_{i} \leq 10^{9} \right)\)

• Dòng 3: Chứa \(q\) số \(n_{1},n_{2},\ldots,n_{q}\ \left( n_{i} \leq 10^{18} \right)\) là các số tiền giả định mà ngân hàng định cho vay.

Kết quả: Gồm \(q\) dòng, mỗi dòng chứa hai số nguyên \(s\) và \(v\), trong đó \(s\) là số lượng sinh viên được vay vốn, \(v\) là số tiền mà sinh viên được vay ít nhất tương ứng với giả định trong dữ liệu vào (Trường hợp \(s = 0\) thì xem như \(v = 0\))

Ví dụ:

Ràng buộc:

• 50% test có \(m,q\ \leq \ 100\);

• 50% test có \(m,q\ \leq \ 10^{4}\)