package main import ( "bufio" "fmt" "os" "sort" ) func main() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n int fmt.Fscan(in, &n) goods := make([][3]int, n) // time, pos, score for i := 0; i < n; i++ { fmt.Fscan(in, &goods[i][0], &goods[i][1], &goods[i][2]) } txs := make([][3]int, 0, n) set := map[int]struct{}{0: {}} // start pos for i := 0; i < n; i++ { t, x, s := goods[i][0], goods[i][1], goods[i][2] if abs(x) <= t { // reachable txs = append(txs, [3]int{t + x, t - x, s}) set[t-x] = struct{}{} } } sort.Slice(txs, func(i, j int) bool { return txs[i][0] < txs[j][0] }) sorted := make([]int, 0, len(set)) for k := range set { sorted = append(sorted, k) } sort.Ints(sorted) mp := make(map[int]int, len(sorted)) for i, v := range sorted { mp[v] = i } seg := NewSegmentTree(make([]E, len(sorted)+10)) for i := 0; i < len(txs); i++ { x, s := txs[i][1], txs[i][2] pos := mp[x] curMax := seg.Query(0, pos+1) + s seg.Set(pos, curMax) } fmt.Fprintln(out, seg.QueryAll()) } func abs(x int) int { if x < 0 { return -x } return x } const INF int = 4e18 // PointSetRangeMax type E = int func (*SegmentTree) e() E { return -INF } func (*SegmentTree) op(a, b E) E { return max(a, b) } func min(a, b int) int { if a < b { return a } return b } func max(a, b int) int { if a > b { return a } return b } type SegmentTree struct { n, size int seg []E } func NewSegmentTree(leaves []E) *SegmentTree { res := &SegmentTree{} n := len(leaves) size := 1 for size < n { size <<= 1 } seg := make([]E, size<<1) for i := 0; i < n; i++ { seg[i+size] = leaves[i] } for i := size - 1; i > 0; i-- { seg[i] = res.op(seg[i<<1], seg[i<<1|1]) } res.n = n res.size = size res.seg = seg return res } func (st *SegmentTree) Get(index int) E { if index < 0 || index >= st.n { return st.e() } return st.seg[index+st.size] } func (st *SegmentTree) Set(index int, value E) { if index < 0 || index >= st.n { return } index += st.size st.seg[index] = value for index >>= 1; index > 0; index >>= 1 { st.seg[index] = st.op(st.seg[index<<1], st.seg[index<<1|1]) } } // [start, end) func (st *SegmentTree) Query(start, end int) E { if start < 0 { start = 0 } if end > st.n { end = st.n } if start >= end { return st.e() } leftRes, rightRes := st.e(), st.e() start += st.size end += st.size for start < end { if start&1 == 1 { leftRes = st.op(leftRes, st.seg[start]) start++ } if end&1 == 1 { end-- rightRes = st.op(st.seg[end], rightRes) } start >>= 1 end >>= 1 } return st.op(leftRes, rightRes) } func (st *SegmentTree) QueryAll() E { return st.seg[1] } // 二分查询最大的 right 使得切片 [left:right] 内的值满足 predicate func (st *SegmentTree) MaxRight(left int, predicate func(E) bool) int { if left == st.n { return st.n } left += st.size res := st.e() for { for left&1 == 0 { left >>= 1 } if !predicate(st.op(res, st.seg[left])) { for left < st.size { left <<= 1 if predicate(st.op(res, st.seg[left])) { res = st.op(res, st.seg[left]) left++ } } return left - st.size } res = st.op(res, st.seg[left]) left++ if (left & -left) == left { break } } return st.n } // 二分查询最小的 left 使得切片 [left:right] 内的值满足 predicate func (st *SegmentTree) MinLeft(right int, predicate func(E) bool) int { if right == 0 { return 0 } right += st.size res := st.e() for { right-- for right > 1 && right&1 == 1 { right >>= 1 } if !predicate(st.op(st.seg[right], res)) { for right < st.size { right = right<<1 | 1 if predicate(st.op(st.seg[right], res)) { res = st.op(st.seg[right], res) right-- } } return right + 1 - st.size } res = st.op(st.seg[right], res) if right&-right == right { break } } return 0 }