← Home
package main

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

type Station struct {
	x int64
	p int64
}

type Segment struct {
	amount int64
	price  int64
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1024*1024), 1024*1024)

	scanInt := func() int64 {
		if !scanner.Scan() {
			return 0
		}
		res := int64(0)
		for _, v := range scanner.Bytes() {
			res = res*10 + int64(v-'0')
		}
		return res
	}

	d := scanInt()
	if d == 0 {
		return
	}
	n := scanInt()
	m := int(scanInt())

	stations := make([]Station, m)
	for i := 0; i < m; i++ {
		stations[i].x = scanInt()
		stations[i].p = scanInt()
	}

	sort.Slice(stations, func(i, j int) bool {
		return stations[i].x < stations[j].x
	})

	stations = append(stations, Station{x: d, p: 0})

	deque := make([]Segment, 0, m+1)
	deque = append(deque, Segment{amount: n, price: 0})

	var pos int64 = 0
	var totalCost int64 = 0

	for _, st := range stations {
		dist := st.x - pos
		if dist > n {
			fmt.Println("-1")
			return
		}

		rem := dist
		for rem > 0 {
			front := &deque[0]
			if front.amount <= rem {
				totalCost += front.amount * front.price
				rem -= front.amount
				deque = deque[1:]
			} else {
				totalCost += rem * front.price
				front.amount -= rem
				rem = 0
			}
		}

		if st.x == d {
			break
		}

		addAmount := dist
		for len(deque) > 0 {
			back := deque[len(deque)-1]
			if back.price >= st.p {
				addAmount += back.amount
				deque = deque[:len(deque)-1]
			} else {
				break
			}
		}
		deque = append(deque, Segment{amount: addAmount, price: st.p})
		pos = st.x
	}

	fmt.Println(totalCost)
}