(define (merge-weighted s1 s2 weight)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else (let ((x1 (stream-car s1))
                    (x2 (stream-car s2)))
                (if (<= (weight x1) (weight x2))
                    (cons-stream x1 (merge-weighted (stream-cdr s1) s2 weight))
                    (cons-stream x2 (merge-weighted s1 (stream-cdr s2) weight)))))))

(define (weighted-pairs s t op)
  (cons-stream
   (cons (stream-car s) (stream-car t))
   (merge-weighted
    (stream-map (lambda (x) (cons (stream-car s) x))
                (stream-cdr t))
    (weighted-pairs (stream-cdr s) (stream-cdr t) op)
    (lambda (x) (op (car x) (cdr x))))))