#-swank
(unless (member :child-sbcl *features*)
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "128MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx opt
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(macrolet ((def (name fname)
             `(define-modify-macro ,name (new-value) ,fname)))
  (def minf min)
  (def maxf max)
  (def mulf *)
  (def divf /)
  (def iorf logior)
  (def xorf logxor)
  (def andf logand))

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  "NOTE: cannot read -2^62"
  (declare #.OPT)
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setq minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48)
                              (* 10 (the (integer 0 #.(floor most-positive-fixnum 10))
                                         result))))
              (return (if minus (- result) result))))))))

(in-package :cl-user)

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;;;
;;; Body
;;;

(declaim (inline bisect-right))
(defun bisect-right (target value &key (start 0) end)
  (declare (integer start)
           ((or null integer) end))
  (macrolet
      ((frob (accessor &optional declaration)
         `(labels
              ((%bisect-right (ng ok)
                 ;; TARGET[OK] > VALUE always holds (assuming
                 ;; TARGET[END] = +infinity)
                 ,@(when declaration (list declaration))
                 (if (<= (- ok ng) 1)
                     ok
                     (let ((mid (ash (+ ng ok) -1)))
                       (if (< value (the fixnum (cdr (,accessor target mid))))
                           (%bisect-right ng mid)
                           (%bisect-right mid ok))))))
            (assert (<= start end))
            (%bisect-right (- start 1) end))))
    (etypecase target
      (vector
       (let ((end (or end (length target))))
         (frob aref (declare ((integer -1 (#.array-total-size-limit)) ng ok)))))
      (function
       (assert end () "Requires END argument if TARGET is a function.")
       (frob funcall)))))

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (boundary 10)
         (vs (make-array n :element-type 'uint31 :initial-element 0))
         (ws (make-array n :element-type 'uint31 :initial-element 0))
         (max-l 0))
    (declare (uint31 n boundary max-l))
    (dotimes (i n)
      (setf (aref vs i) (read-fixnum)
            (aref ws i) (read-fixnum)))
    (let* ((q (read))
           (query-store (make-array n :element-type 'list :initial-element nil))
           (res (make-array q :element-type 'fixnum :initial-element 0))
           (tree (make-array (* 3 n) :element-type 'bit :initial-element 1)))
      (dotimes (i q)
        (let ((v (- (read-fixnum) 1))
              (l (read-fixnum)))
          (maxf max-l l)
          (push (list v l i) (aref query-store v))))
      (sb-int:named-let recur ((i 0))
        (declare (uint31 i))
        (if (>= i n)
            nil
            (let ((res1 (recur (+ (* i 2) 1)))
                  (res2 (recur (+ (* i 2) 2))))
              (when (or (aref query-store i)
                        res1 res2)
                (setf (aref tree i) 1)))))
      (labels ((make (half2 v w)
                 (declare ((simple-array list (*)) half2)
                          (uint31 v w))
                 (let* ((new-half2 (make-array (* 2 (length half2)) :element-type 'list))
                        (len (length half2))
                        (pos1 0)
                        (pos2 0)
                        (end 0)
                        (current-w -1)
                        (current-v -1))
                   (declare ((simple-array list (*)) new-half2)
                            (uint31 pos1 pos2 end)
                            (fixnum current-w current-v))
                   (loop (when (= pos1 len)
                           (loop for pos from pos2 below len
                                 for (v2 . w2) of-type (uint62 . uint62) = (aref half2 pos)
                                 when (and (> (+ v2 v) current-v)
                                           (> (+ w2 w) current-w))
                                 do (setf (aref new-half2 end) (cons (the fixnum (+ v2 v))
                                                                     (the fixnum (+ w2 w)))
                                          end (+ end 1)
                                          current-w (+ w2 w)
                                          current-v (+ v2 v)))
                           (return))
                         (destructuring-bind (v1 . w1) (aref half2 pos1)
                           (destructuring-bind (v2 . w2) (aref half2 pos2)
                             (declare (uint62 v1 v2 w1 w2))
                             (cond ((< w1 (+ w2 w))
                                    (when (and (> w1 current-w)
                                               (> v1 current-v))
                                      (setf (aref new-half2 end) (cons v1 w1)
                                            end (+ end 1)
                                            current-w w1
                                            current-v v1))
                                    (incf pos1))
                                   ((> w1 (+ w2 w))
                                    (when (and (> (+ w2 w) current-w)
                                               (> (+ v2 v) current-v))
                                      (setf (aref new-half2 end) (cons (the fixnum (+ v2 v))
                                                                       (the fixnum (+ w2 w)))
                                            end (+ end 1)
                                            current-w (+ w2 w)
                                            current-v (+ v2 v)))
                                    (incf pos2))
                                   ((= w1 (+ w2 w))
                                    (let ((max-v (max v1 (+ v2 v))))
                                      (declare (uint62 max-v))
                                      (when (and (> w1 current-w)
                                                 (> max-v current-v))
                                        (setf (aref new-half2 end) (cons max-v w1)
                                              end (+ end 1)
                                              current-w w1
                                              current-v max-v))
                                      (incf pos1)
                                      (incf pos2)))
                                   (t (error "Huh?"))))))
                   (adjust-array new-half2 end))))
        (sb-int:named-let recur ((i 0)
                                 (depth 0)
                                 (half1 (make-array 1
                                                    :element-type 'list
                                                    :initial-element (cons 0 0)))
                                 (half2 (make-array 1
                                                    :element-type 'list
                                                    :initial-element (cons 0 0))))
          (declare (uint31 i depth)
                   ((simple-array list (*)) half1 half2))
          (when (>= i n) (return-from recur))
          (let ((v (aref vs i))
                (w (aref ws i)))
            (declare (uint31 v w))
            (if (< depth boundary)
                (let ((new-half1 (make half1 v w)))
                  (declare ((simple-array list (*)) new-half1))
                  (loop for (q-v q-l index) of-type (uint62 uint62 uint62) in (aref query-store i)
                        for pos = (- (bisect-right new-half1 q-l) 1)
                        do (setf (aref res index) (car (aref new-half1 pos))))
                  (when (= 1 (aref tree (+ (* i 2) 1)))
                    (recur (+ (* i 2) 1) (+ depth 1) new-half1 half2))
                  (when (= 1 (aref tree (+ (* i 2) 2)))
                    (recur (+ (* i 2) 2) (+ depth 1) new-half1 half2)))
                (let* ((new-half2 (make half2 v w)))
                  (declare ((simple-array list (*)) new-half2))
                  ;; answer query
                  ;; 各重みについて最大の価値しかいらない
                  (if (aref query-store i)
                      (progn
                        (loop
                          for (q-v q-l index) of-type (uint62 uint62 uint62) in (aref query-store i)
                          for max-value of-type fixnum = 0
                          for pos2 = (- (length new-half2) 1)
                          do (loop for (v1 . w1) of-type (fixnum . fixnum) across half1
                                   ;; 重さがl-w1以下のものを見つける
                                   while (<= w1 q-l)
                                   do (loop
                                        (destructuring-bind (v2 . w2) (aref new-half2 pos2)
                                          (declare (fixnum v2 w2))
                                          (when (<= (+ w1 w2) q-l)
                                            (return))
                                          (decf pos2)))
                                      (destructuring-bind (v2 . w2) (aref new-half2 pos2)
                                        (declare (fixnum v2 w2))
                                        (maxf max-value (+ v1 v2))))
                             (setf (aref res index) max-value))
                        (when (= 1 (aref tree (+ (* i 2) 1)))
                          (recur (+ (* i 2) 1) (+ depth 1) half1 new-half2))
                        (when (= 1 (aref tree (+ (* i 2) 2)))
                          (recur (+ (* i 2) 2) (+ depth 1) half1 new-half2)))
                      (progn
                        (when (= 1 (aref tree (+ (* i 2) 1)))
                          (recur (+ (* i 2) 1) (+ depth 1) half1 new-half2))
                        (when (= 1 (aref tree (+ (* i 2) 2)))
                          (recur (+ (* i 2) 2) (+ depth 1) half1 new-half2)))))))))
      (write-string
       (with-output-to-string (*standard-output* nil :element-type 'base-char)
         (map () #'println res))))))

#-swank (main)

;;;
;;; Test and benchmark
;;;

#+swank
(defun io-equal (in-string out-string &key (function #'main) (test #'equal))
  "Passes IN-STRING to *STANDARD-INPUT*, executes FUNCTION, and returns true if
the string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
  (labels ((ensure-last-lf (s)
             (if (eql (uiop:last-char s) #\Linefeed)
                 s
                 (uiop:strcat s uiop:+lf+))))
    (funcall test
             (ensure-last-lf out-string)
             (with-output-to-string (out)
               (let ((*standard-output* out))
                 (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                   (funcall function)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    (run-program "powershell.exe" '("-Command" "Get-Clipboard") :output out :search t)))

#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))

#+swank
(defun run (&optional thing (out *standard-output*))
  "THING := null | string | symbol | pathname

null: run #'MAIN using the text on clipboard as input.
string: run #'MAIN using the string as input.
symbol: alias of FIVEAM:RUN!.
pathname: run #'MAIN using the text file as input."
  (let ((*standard-output* out))
    (etypecase thing
      (null
       (with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
         (main)))
      (string
       (with-input-from-string (*standard-input* (delete #\Return thing))
         (main)))
      (symbol (5am:run! thing))
      (pathname
       (with-open-file (*standard-input* thing)
         (main))))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (let ((n 262143))
      (format out "~D~%" n)
      (dotimes (_ n)
        (format out "~D ~D~%" (+ 1 (random 100000)) (+ 1 (random 100000))))
      (println 100000 out)
      (dotimes (_ 100000)
        (format out "~D ~D~%" (+ 130000 (random (- n 130000))) (+ 1 (random 100000)))))))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "3
1 2
2 3
3 4
3
1 1
2 5
3 5
"
    "0
3
3
"))
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "15
123 119
129 120
132 112
126 109
118 103
115 109
102 100
130 120
105 105
132 115
104 102
107 107
127 116
121 104
121 115
8
8 234
9 244
10 226
11 227
12 240
13 237
14 206
15 227
"
    "256
255
250
247
255
259
223
253
")))


Measured memory_bytes: 93032