← Home
```go
package main

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

func main() {
	reader := bufio.NewReader(os.Stdin)

	var n, m, p int
	fmt.Fscan(reader, &n, &m, &p)

	type weapon struct {
		a, ca int
	}
	type armor struct {
		b, cb int
	}
	type monster struct {
		x, y, z int
	}

	weapons := make([]weapon, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &weapons[i].a, &weapons[i].ca)
	}

	armors := make([]armor, m)
	for i := 0; i < m; i++ {
		fmt.Fscan(reader, &armors[i].b, &armors[i].cb)
	}

	monsters := make([]monster, p)
	for i := 0; i < p; i++ {
		fmt.Fscan(reader, &monsters[i].x, &monsters[i].y, &monsters[i].z)
	}

	// Sort weapons by attack modifier
	sort.Slice(weapons, func(i, j int) bool {
		return weapons[i].a < weapons[j].a
	})

	// Sort armors by defense modifier
	sort.Slice(armors, func(i, j int) bool {
		return armors[i].b < armors[j].b
	})

	// Sort monsters by defense (x) value
	sort.Slice(monsters, func(i, j int) bool {
		return monsters[i].x < monsters[j].x
	})

	// For armors, we need a segment tree that supports:
	// - point update: add value to a position
	// - range max query
	// But we want: for each weapon, we add monsters it can defeat,
	// and query the best armor choice.

	// For each armor index j, the segment tree stores:
	//   (sum of z_k for monsters defeated so far with b_j > y_k) - cb_j
	// We want to maximize this over all j.

	// We process weapons in increasing order of attack.
	// For each weapon, we add new monsters that this weapon can defeat (a_i > x_k).
	// When we add a monster with attack y_k, we need to add z_k to all armor indices j
	// where b_j > y_k. Since armors are sorted, this is a suffix update.

	// Segment tree with lazy propagation for range add and range max query.

	size := m
	tree := make([]int64, 4*size)
	lazy := make([]int64, 4*size)

	for i := range tree {
		tree[i] = math.MinInt64
	}

	var build func(node, l, r int)
	build = func(node, l, r int) {
		if l == r {
			tree[node] = int64(-armors[l].cb)
			return
		}
		mid := (l + r) / 2
		build(2*node, l, mid)
		build(2*node+1, mid+1, r)
		tree[node] = max64(tree[2*node], tree[2*node+1])
	}

	var pushDown func(node int)
	pushDown = func(node int) {
		if lazy[node] != 0 {
			for _, child := range []int{2 * node, 2*node + 1} {
				tree[child] += lazy[node]
				lazy[child] += lazy[node]
			}
			lazy[node] = 0
		}
	}

	var update func(node, l, r, ql, qr int, val int64)
	update = func(node, l, r, ql, qr int, val int64) {
		if ql > qr || l > qr || r < ql {
			return
		}
		if ql <= l && r <= qr {
			tree[node] += val
			lazy[node] += val
			return
		}
		pushDown(node)
		mid := (l + r) / 2
		update(2*node, l, mid, ql, qr, val)
		update(2*node+1, mid+1, r, ql, qr, val)
		tree[node] = max64(tree[2*node], tree[2*node+1])
	}

	build(1, 0, m-1)

	ans := int64(math.MinInt64)
	mi := 0 // monster index

	// For each weapon in sorted order
	// We also want minimum cost weapon for each attack value
	// Actually, we should deduplicate weapons: for same attack, keep min cost
	// But actually we iterate all weapons and just check each one.

	// Better: for same attack value, only the cheapest matters
	bestWeaponCost := make(map[int]int)
	for _, w := range weapons {
		if c, ok := bestWeaponCost[w.a]; !ok || w.ca < c {
			bestWeaponCost[w.a] = w.ca
		}
	}
	type wp struct{ a, ca int }
	uniqueWeapons := make([]wp, 0, len(bestWeaponCost))
	for a, ca := range bestWeaponCost {
		uniqueWeapons = append(uniqueWeapons, wp{a, ca})
	}
	sort.Slice(uniqueWeapons, func(i, j int) bool { return uniqueWeapons[i].a < uniqueWeapons[j].a })

	for _, w := range uniqueWeapons {
		for mi < p && monsters[mi].x < w.a {
			mon := monsters[mi]
			// Add mon.z to all armors with b > mon.y
			idx := sort.Search(m, func(i int) bool { return armors[i].b > mon.y })
			if idx < m {
				update(1, 0, m-1, idx, m-1, int64(mon.z))
			}
			mi++
		}
		val := tree[1] - int64(w.ca)
		if val > ans {
			ans = val
		}
	}

	fmt.Println(ans)
}

func max64(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}
```