```go
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

type Node struct {
	left, right *Node
	pr          uint64
	size        int
	maxK        int64
	valK        int64
	id          int
}

func sz(n *Node) int {
	if n == nil {
		return 0
	}
	return n.size
}

func mx(n *Node) int64 {
	if n == nil {
		return -1 << 60
	}
	return n.maxK
}

func upd(n *Node) {
	if n == nil {
		return
	}
	n.size = 1 + sz(n.left) + sz(n.right)
	n.maxK = n.valK
	if m := mx(n.left); m > n.maxK {
		n.maxK = m
	}
	if m := mx(n.right); m > n.maxK {
		n.maxK = m
	}
}

var seed uint64 = 88172645463393265

func rng() uint64 {
	seed ^= seed << 7
	seed ^= seed >> 9
	return seed
}

func merge(a, b *Node) *Node {
	if a == nil {
		return b
	}
	if b == nil {
		return a
	}
	if a.pr < b.pr {
		a.right = merge(a.right, b)
		upd(a)
		return a
	} else {
		b.left = merge(a, b.left)
		upd(b)
		return b
	}
}

func splitBySize(root *Node, leftSize int) (*Node, *Node) {
	if root == nil {
		return nil, nil
	}
	if sz(root.left) >= leftSize {
		l, r := splitBySize(root.left, leftSize)
		root.left = r
		upd(root)
		return l, root
	} else {
		l, r := splitBySize(root.right, leftSize-sz(root.left)-1)
		root.right = l
		upd(root)
		return root, r
	}
}

func findLastGe(n *Node, thr int64) int {
	if n == nil || n.maxK < thr {
		return 0
	}
	if n.right != nil && n.right.maxK >= thr {
		r := findLastGe(n.right, thr)
		return sz(n.left) + 1 + r
	}
	if n.valK >= thr {
		return sz(n.left) + 1
	}
	return findLastGe(n.left, thr)
}

type FastReader struct {
	r *bufio.Reader
}

func NewFastReader() *FastReader {
	return &FastReader{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}

func (fr *FastReader) nextInt() int {
	sign := 1
	val := 0
	c, err := fr.r.ReadByte()
	for (c < '0' || c > '9') && c != '-' {
		c, err = fr.r.ReadByte()
		if err != nil {
			return 0
		}
	}
	if c == '-' {
		sign = -1
		c, _ = fr.r.ReadByte()
	}
	for c >= '0' && c <= '9' {
		val = val*10 + int(c-'0')
		c, err = fr.r.ReadByte()
		if err != nil {
			break
		}
	}
	return val * sign
}

func (fr *FastReader) nextInt64() int64 {
	sign := int64(1)
	var val int64 = 0
	c, err := fr.r.ReadByte()
	for (c < '0' || c > '9') && c != '-' {
		c, err = fr.r.ReadByte()
		if err != nil {
			return 0
		}
	}
	if c == '-' {
		sign = -1
		c, _ = fr.r.ReadByte()
	}
	for c >= '0' && c <= '9' {
		val = val*10 + int64(c-'0')
		c, err = fr.r.ReadByte()
		if err != nil {
			break
		}
	}
	return val * sign
}

type Event struct {
	s  int
	id int
}

func main() {
	in := NewFastReader()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	t := in.nextInt()
	for ; t > 0; t-- {
		n := in.nextInt()
		D := in.nextInt()
		k := make([]int64, n)
		s := make([]int, n)
		for i := 0; i < n; i++ {
			k[i] = in.nextInt64()
			s[i] = in.nextInt()
		}

		var root *Node
		for i := 0; i < n; i++ {
			node := &Node{valK: k[i], id: i, pr: rng()}
			upd(node)
			root = merge(root, node)
		}

		events := make([][]Event, D+2)
		firstServe := make([]int, n)
		cntServed := 0
		ans := -1

		for minute := 1; minute <= D; minute++ {
			if root != nil {
				left, right := splitBySize(root, 1)
				root = right
				servedID := left.id
				if firstServe[servedID] == 0 {
					firstServe[servedID] = minute
					cntServed++
					if cntServed == n {
						ans = minute
						break
					}
				}
				tr := minute + s[servedID]
				if tr <= D {
					events[tr] = append(events[tr], Event{s: s[servedID], id: servedID})
				}
			}
			if len(events[minute]) > 1 {
				sort.Slice(events[minute], func(i, j int) bool {
					if events[minute][i].s != events[minute][j].s {
						return events[minute][i].s < events[minute][j].s
					}
					return events[minute][i].id < events[minute][j].id
				})
			}
			for _, e := range events[minute] {
				idx := findLastGe(root, k[e.id])
				l, r := splitBySize(root, idx)
				node := &Node{valK: k[e.id], id: e.id, pr: rng()}
				upd(node)
				root = merge(merge(l, node), r)
			}
		}

		fmt.Fprintln(out, ans)
	}
}
```