{.push hints:off.}
import algorithm, hashes, macros, math, sequtils, sets, strutils, tables, times, unicode
when NimMajor <= 0 and NimMinor <= 17: import future else: import sugar
when NimMajor <= 0 and NimMinor <= 17: import queues

macro unpack(rhs: seq, cnt: static[int]): auto =
  let t = genSym(); result = quote do:(let `t` = `rhs`;())
  when NimMajor <= 0 and NimMinor <= 17:
    for i in 0..<cnt: result[0][1].add(quote do:`t`[`i`])
  else:
    for i in 0..<cnt: result[1].add(quote do:`t`[`i`])
 
template input(T: typedesc, cnt: Natural = 1): untyped =
  let line = stdin.readLine.split(" ")
  when T is int:         line.map(parseInt).unpack(cnt)
  elif T is float:       line.map(parseFloat).unpack(cnt)
  elif T is string:      line.unpack(cnt)
  elif T is char:        line.mapIt(it[0]).unpack(cnt)
  elif T is seq[int]:    line.map(parseInt)
  elif T is seq[float]:  line.map(parseFloat)
  elif T is seq[string]: line
  elif T is seq[char]:   line.mapIt(it[0])

proc floorMod*[T: SomeNumber](x, y: T): T =
  result = x mod y
  if (result > 0 and y < 0) or (result < 0 and y > 0): result += y

proc `%`(n,m:int):int = floorMod(n,m)
proc `%=`(n: var int, m: int)  = n = floorMod(n,m)
proc `//=`(n: var int, m: int) = n = n div m
proc `<<=`(n: var int, m: int) = n = n shl m
proc `>>=`(n: var int, m: int) = n = n shr m
proc `:<=`[T](n: var T, m: T):bool {.discardable.}=
  result = n > m
  if result:
    n = m
proc `:>=`[T](n: var T, m: T):bool {.discardable.}=
  result = n < m
  if result:
    n = m
proc newSeq2[T](n1, n2: Natural): seq[seq[T]] = newSeqWith(n1, newSeq[T](n2))
proc newSeq3[T](n1, n2, n3: Natural): seq[seq[seq[T]]] = newSeqWith(n1, newSeqWith(n2, newSeq[T](n3)))
proc spacingStr(things: varargs[string,`$`]):string =
  result = ""
  for thing in things:
    result &= thing
    result &= " "
  result &= "\n"
proc spacingStr[T](things: seq[T]):string =
  result = ""
  for thing in things:
    result &= $thing
    result &= " "
  result &= "\n"
proc spacingStr[T](things: seq[seq[T]]):string =
  result = ""
  for thing in things:
    result &= spacingStr(thing)
proc spacingStrPlusOne(things: varargs[int]):string =
  result = ""
  for thing in things:
    result &= $(thing+1)
    result &= " "
  result &= "\n"
proc spacingStrPlusOne[T](things: seq[T]):string =
  result = ""
  for thing in things:
    result &= $(thing+1)
    result &= " "
  result &= "\n"
proc spacingStrPlusOne[T](things: seq[seq[T]]):string =
  result = ""
  for thing in things:
    result &= spacingStrPlusOne(thing)
proc spacingEcho(things: varargs[string,`$`]) = stdout.write(spacingStr(things))
proc spacingEcho[T](things: seq[T]) = stdout.write(spacingStr(things))
proc spacingEcho[T](things: seq[seq[T]]) = stdout.write(spacingStr(things))
proc spacingEchoPlusOne(things: varargs[int]) = stdout.write(spacingStrPlusOne(things))
proc spacingEchoPlusOne(things: seq[int]) = stdout.write(spacingStrPlusOne(things))
proc spacingEchoPlusOne(things: seq[seq[int]]) = stdout.write(spacingStrPlusOne(things))
template myDump*(things: varargs[string,`$`]) =
  when NimMajor > 0 or NimMinor > 17:
    let sr = spacingStr(things)
    let line = instantiationInfo().line
    let lineName = "LINE" & '0'.repeat(4-($line).len) & ($line) & "...>  "
    stdout.write(lineName & sr)
template myDump*[T](things: seq[T]) =
  when NimMajor > 0 or NimMinor > 17:
    let sr = spacingStr(things)
    let line = instantiationInfo().line
    let lineName = "LINE" & '0'.repeat(4-($line).len) & ($line) & "...>  "
    stdout.write(lineName & sr)
template myDump*[T](things: seq[seq[T]]) =
  when NimMajor > 0 or NimMinor > 17:
    let sr = spacingStr(things)
    let line = instantiationInfo().line
    let lineName = "LINE" & '0'.repeat(4-($line).len) & ($line) & "...v\n"
    stdout.write(lineName & sr)
iterator items(n:int):int = 
  for i in 0..<n:
    yield i
{.pop.}

# -------------------------------------------------- #
#
#            Nim's Runtime Library
#        (c) Copyright 2012 Andreas Rumpf
#


import math, typetraits

type
  Deque*[T] = object
    ## A double-ended queue backed with a ringed seq buffer.
    data: seq[T]
    head, tail, count, mask: int

proc initDeque*[T](initialSize: int = 4): Deque[T] =
  ## Create a new deque.
  ## Optionally, the initial capacity can be reserved via `initialSize` as a
  ## performance optimization. The length of a newly created deque will still
  ## be 0.
  ##
  ## `initialSize` needs to be a power of two. If you need to accept runtime
  ## values for this you could use the ``nextPowerOfTwo`` proc from the
  ## `math <math.html>`_ module.
  assert isPowerOfTwo(initialSize)
  result.mask = initialSize-1
  newSeq(result.data, initialSize)

proc len*[T](deq: Deque[T]): int {.inline.} =
  ## Return the number of elements of `deq`.
  result = deq.count

template emptyCheck(deq) =
  # Bounds check for the regular deque access.
  when compileOption("boundChecks"):
    if unlikely(deq.count < 1):
      raise newException(IndexError, "Empty deque.")

template xBoundsCheck(deq, i) =
  # Bounds check for the array like accesses.
  when compileOption("boundChecks"):  # d:release should disable this.
    if unlikely(i >= deq.count):  # x < deq.low is taken care by the Natural parameter
      raise newException(IndexError,
                         "Out of bounds: " & $i & " > " & $(deq.count - 1))

proc `[]`*[T](deq: Deque[T], i: Natural) : T {.inline.} =
  ## Access the i-th element of `deq` by order from first to last.
  ## deq[0] is the first, deq[^1] is the last.
  xBoundsCheck(deq, i)
  return deq.data[(deq.head + i) and deq.mask]

proc `[]`*[T](deq: var Deque[T], i: Natural): var T {.inline.} =
  ## Access the i-th element of `deq` and returns a mutable
  ## reference to it.
  xBoundsCheck(deq, i)
  return deq.data[(deq.head + i) and deq.mask]

proc `[]=`* [T] (deq: var Deque[T], i: Natural, val : T) {.inline.} =
  ## Change the i-th element of `deq`.
  xBoundsCheck(deq, i)
  deq.data[(deq.head + i) and deq.mask] = val

iterator items*[T](deq: Deque[T]): T =
  ## Yield every element of `deq`.
  var i = deq.head
  for c in 0 ..< deq.count:
    yield deq.data[i]
    i = (i + 1) and deq.mask

iterator mitems*[T](deq: var Deque[T]): var T =
  ## Yield every element of `deq`.
  var i = deq.head
  for c in 0 ..< deq.count:
    yield deq.data[i]
    i = (i + 1) and deq.mask

iterator pairs*[T](deq: Deque[T]): tuple[key: int, val: T] =
  ## Yield every (position, value) of `deq`.
  var i = deq.head
  for c in 0 ..< deq.count:
    yield (c, deq.data[i])
    i = (i + 1) and deq.mask

proc contains*[T](deq: Deque[T], item: T): bool {.inline.} =
  ## Return true if `item` is in `deq` or false if not found. Usually used
  ## via the ``in`` operator. It is the equivalent of ``deq.find(item) >= 0``.
  ##
  ## .. code-block:: Nim
  ##   if x in q:
  ##     assert q.contains x
  for e in deq:
    if e == item: return true
  return false

proc expandIfNeeded[T](deq: var Deque[T]) =
  var cap = deq.mask + 1
  if unlikely(deq.count >= cap):
    var n = newSeq[T](cap * 2)
    for i, x in pairs(deq):  # don't use copyMem because the GC and because it's slower.
      shallowCopy(n[i], x)
    shallowCopy(deq.data, n)
    deq.mask = cap * 2 - 1
    deq.tail = deq.count
    deq.head = 0

proc addFirst*[T](deq: var Deque[T], item: T) =
  ## Add an `item` to the beginning of the `deq`.
  expandIfNeeded(deq)
  inc deq.count
  deq.head = (deq.head - 1) and deq.mask
  deq.data[deq.head] = item

proc addLast*[T](deq: var Deque[T], item: T) =
  ## Add an `item` to the end of the `deq`.
  expandIfNeeded(deq)
  inc deq.count
  deq.data[deq.tail] = item
  deq.tail = (deq.tail + 1) and deq.mask

proc peekFirst*[T](deq: Deque[T]): T {.inline.}=
  ## Returns the first element of `deq`, but does not remove it from the deque.
  emptyCheck(deq)
  result = deq.data[deq.head]

proc peekLast*[T](deq: Deque[T]): T {.inline.} =
  ## Returns the last element of `deq`, but does not remove it from the deque.
  emptyCheck(deq)
  result = deq.data[(deq.tail - 1) and deq.mask]

template destroy(x: untyped) =
  reset(x)

proc popFirst*[T](deq: var Deque[T]): T {.inline, discardable.} =
  ## Remove and returns the first element of the `deq`.
  emptyCheck(deq)
  dec deq.count
  result = deq.data[deq.head]
  destroy(deq.data[deq.head])
  deq.head = (deq.head + 1) and deq.mask

proc popLast*[T](deq: var Deque[T]): T {.inline, discardable.} =
  ## Remove and returns the last element of the `deq`.
  emptyCheck(deq)
  dec deq.count
  deq.tail = (deq.tail - 1) and deq.mask
  result = deq.data[deq.tail]
  destroy(deq.data[deq.tail])

proc clear*[T](deq: var Deque[T]) {.inline.} =
  ## Resets the deque so that it is empty.
  for el in mitems(deq): destroy(el)
  deq.count = 0
  deq.tail = deq.head

proc shrink*[T](deq: var Deque[T], fromFirst = 0, fromLast = 0) =
  ## Remove `fromFirst` elements from the front of the deque and
  ## `fromLast` elements from the back. If the supplied number of
  ## elements exceeds the total number of elements in the deque,
  ## the deque will remain empty.
  ##
  ## Any user defined destructors
  if fromFirst + fromLast > deq.count:
    clear(deq)
    return

  for i in 0 ..< fromFirst:
    destroy(deq.data[deq.head])
    deq.head = (deq.head + 1) and deq.mask

  for i in 0 ..< fromLast:
    destroy(deq.data[deq.tail])
    deq.tail = (deq.tail - 1) and deq.mask

  dec deq.count, fromFirst + fromLast

proc `$`*[T](deq: Deque[T]): string =
  ## Turn a deque into its string representation.
  result = "["
  for x in deq:
    if result.len > 1: result.add(", ")
    result.addQuoted(x)
  result.add("]")

# -------------------------------------------------- #
import sequtils

# -------------------------------------------------- #

#
#            Nim's Runtime Library
#        (c) Copyright 2017 Andreas Rumpf
#
#    See the file "copying.txt", included in this
#    distribution, for details about the copyright.
#

## Nim's standard random number generator. Based on
## the ``xoroshiro128+`` (xor/rotate/shift/rotate) library.
## * More information: http://xoroshiro.di.unimi.it/
## * C implementation: http://xoroshiro.di.unimi.it/xoroshiro128plus.c
##
## **Do not use this module for cryptographic purposes!**

include "system/inclrtl"
{.push debugger:off.}

when defined(JS):
  type ui = uint32
  const randMax = 4_294_967_295u32
else:
  type ui = uint64
  const randMax = 18_446_744_073_709_551_615u64

type
  Rand* = object ## State of the random number generator.
                 ## The procs that use the default state
                 ## are **not** thread-safe!
    a0, a1: ui

when defined(JS):
  var state = Rand(
    a0: 0x69B4C98Cu32,
    a1: 0xFED1DD30u32) # global for backwards compatibility
else:
  # racy for multi-threading but good enough for now:
  var state = Rand(
    a0: 0x69B4C98CB8530805u64,
    a1: 0xFED1DD3004688D67CAu64) # global for backwards compatibility

proc rotl(x, k: ui): ui =
  result = (x shl k) or (x shr (ui(64) - k))

proc next*(r: var Rand): uint64 =
  ## Uses the state to compute a new ``uint64`` random number.
  let s0 = r.a0
  var s1 = r.a1
  result = s0 + s1
  s1 = s1 xor s0
  r.a0 = rotl(s0, 55) xor s1 xor (s1 shl 14) # a, b
  r.a1 = rotl(s1, 36) # c

proc skipRandomNumbers*(s: var Rand) =
  ## This is the jump function for the generator. It is equivalent
  ## to 2^64 calls to next(); it can be used to generate 2^64
  ## non-overlapping subsequences for parallel computations.
  when defined(JS):
    const helper = [0xbeac0467u32, 0xd86b048bu32]
  else:
    const helper = [0xbeac0467eba5facbu64, 0xd86b048b86aa9922u64]
  var
    s0 = ui 0
    s1 = ui 0
  for i in 0..high(helper):
    for b in 0 ..< 64:
      if (helper[i] and (ui(1) shl ui(b))) != 0:
        s0 = s0 xor s.a0
        s1 = s1 xor s.a1
      discard next(s)
  s.a0 = s0
  s.a1 = s1

proc rand*(r: var Rand; max: Natural): int {.benign.} =
  ## Returns a random number in the range 0..max. The sequence of
  ## random number is always the same, unless `randomize` is called
  ## which initializes the random number generator with a "random"
  ## number, i.e. a tickcount.
  if max == 0: return
  while true:
    let x = next(r)
    if x <= randMax - (randMax mod ui(max)):
      return int(x mod (uint64(max)+1u64))

proc rand*(max: int): int {.benign.} =
  ## Returns a random number in the range 0..max. The sequence of
  ## random number is always the same, unless `randomize` is called
  ## which initializes the random number generator with a "random"
  ## number, i.e. a tickcount.
  rand(state, max)

proc rand*[T](r: var Rand; x: Slice[T]): T =
  ## For a slice `a .. b` returns a value in the range `a .. b`.
  result = T(rand(r, x.b - x.a)) + x.a

proc rand*[T](x: Slice[T]): T =
  ## For a slice `a .. b` returns a value in the range `a .. b`.
  result = rand(state, x)

proc rand*(r: var Rand; max:float): float {.benign.} =
  ## Returns a random number in the range 0..max. The sequence of
  ## random number is always the same, unless `randomize` is called
  ## which initializes the random number generator with a "random"
  ## number, i.e. a tickcount.
  let x = next(r)
  when defined(JS):
    result = (float(x) / float(high(uint32))) * max
  else:
    let u = (0x3FFu64 shl 52u64) or (x shr 12u64)
    result = (cast[float](u) - 1.0) * max

proc rand*(max: float): float {.benign.} =
  ## Returns a random number in the range 0..max. The sequence of
  ## random number is always the same, unless `randomize` is called
  ## which initializes the random number generator with a "random"
  ## number, i.e. a tickcount.
  rand(state, max)

proc rand*[T](r: var Rand; a: openArray[T]): T =
  ## returns a random element from the openarray `a`.
  result = a[rand(r, a.low..a.high)]

proc rand*[T](a: openArray[T]): T =
  ## returns a random element from the openarray `a`.
  result = a[rand(a.low..a.high)]


proc initRand*(seed: int64): Rand =
  ## Creates a new ``Rand`` state from ``seed``.
  result.a0 = ui(seed shr 16)
  result.a1 = ui(seed and 0xffff)
  discard next(result)

proc randomize*(seed: int64) {.benign.} =
  ## Initializes the default random number generator
  ## with a specific seed.
  state = initRand(seed)

proc shuffle*[T](r: var Rand; x: var openArray[T]) =
  ## Swaps the positions of elements in a sequence randomly.
  for i in countdown(x.high, 1):
    let j = r.rand(i)
    swap(x[i], x[j])

proc shuffle*[T](x: var openArray[T]) =
  ## Swaps the positions of elements in a sequence randomly.
  shuffle(state, x)


{.pop.}

# -------------------------------------------------- #

type Kouho = tuple
  po:int
  cost:int

proc bstOrderRelation(x,y:Kouho):bool = x.po < y.po
const bitOrderWorsts = [(po:999999)]
const bitOrderRelations = [bstOrderRelation]

# -------------------------------------------------- #

type RichNodeObj*[T] = object
  value: T
  lp: ref RichNodeObj[T]
  rp: ref RichNodeObj[T]
  lc: ref RichNodeObj[T]
  rc: ref RichNodeObj[T]
  size: int # number of nodes under (include itself)
  order_bests: array[bitOrderRelations.len,T]

type RichNode*[T] = ref RichNodeObj[T]

proc newRichNode*[T](value:T):RichNode[T] =
  result = RichNode[T](value:value,size:1)
  for d in 0..<bitOrderRelations.len:
    result.order_bests[d] = value

proc recalc_after_update[T](u: var RichNode[T]) =
  u.size = u.lc.len + 1 + u.rc.len
  for d in 0..<bitOrderRelations.len:
    u.order_bests[d] = u.value
  if u.lc != nil:
    for d,relation in bitOrderRelations:
      if relation(u.lc.order_bests[d], u.order_bests[d]):
        u.order_bests[d] = u.lc.order_bests[d]
  if u.rc != nil:
    for d,relation in bitOrderRelations:
      if relation(u.rc.order_bests[d], u.order_bests[d]):
        u.order_bests[d] = u.rc.order_bests[d]

proc replace_lc_of_root[T](u:var RichNode[T], new_lc:RichNode[T]) =
  if u.lc != nil:
    u.lc.rp = nil
  u.lc = new_lc
  if new_lc != nil:
    new_lc.rp = u
  u.recalc_after_update()

proc replace_rc_of_root[T](u:var RichNode[T], new_rc:RichNode[T]) =
  if u.rc != nil:
    u.rc.lp = nil
  u.rc = new_rc
  if new_rc != nil:
    new_rc.lp = u
  u.size = u.lc.len + 1 + u.rc.len
  u.recalc_after_update()

proc head*[T](t:RichNode[T]):RichNode[T] =
  if t == nil:
    return t
  result = t
  while result.lc != nil:
    result = result.lc

proc tail*[T](t:RichNode[T]):RichNode[T] =
  if t == nil:
    return t
  result = t
  while result.rc != nil:
    result = result.rc

proc next*[T](t:RichNode[T]):RichNode[T] =
  if t.rc != nil:
    result = t.rc
    while result.lc != nil:
      result = result.lc
  else:
    result = t
    while result.rp == nil:
      if result.lp == nil:
        return nil
      result = result.lp
    return result.rp

proc prev*[T](t:RichNode[T]):RichNode[T] =
  if t.lc != nil:
    result = t.lc
    while result.rc != nil:
      result = result.rc
  else:
    result = t
    while result.lp == nil:
      if result.rp == nil:
        return nil
      result = result.rp
    return result.lp

proc len*[T](t:RichNode[T]):int =
  if t == nil:
    0
  else:
    t.size

proc `[]`*[T](t:RichNode[T], k:int): RichNode[T] =
  var k = k
  if t.lc.len > k:
    return t.lc[k]
  k = k - t.lc.len
  if k == 0:
    return t
  k = k - 1
  if t.rc.len > k:
    return t.rc[k]
  return nil

proc `[]=`*[T](t:var RichNode[T], k:int, x:T) =
  var k = k
  if t.lc.len > k:
    t.lc[k] = x
    t.recalc_after_update()
    return
  k = k - t.lc.len
  if k == 0:
    t.value = x
    t.recalc_after_update()
    return
  k = k - 1
  if t.rc.len > k:
    t.rc[k] = x
    t.recalc_after_update()
    return

iterator nodes*[T](t:RichNode[T]): RichNode[T] =
  if t.len != 0:
    var result = t.head()
    let tail = t.tail()
    yield result
    while result != tail:
      result = result.next()
      yield result

iterator pairs*[T](t:RichNode[T]): (RichNode[T], T) =
  # can be used as "for k,v in t:"
  for node in t.nodes:
    yield (node, node.value)

iterator values*[T](t:RichNode[T]): T =
  for node in t.nodes:
    yield node.value

iterator items*[T](t:RichNode[T]): RichNode[T] =
  # can be used as "for k in t:"
  for node in t.nodes:
    yield node

iterator reversed_nodes*[T](t:RichNode[T]): RichNode[T] =
  var result = t.tail()
  let head = t.head()
  yield result
  while result != head:
    result = result.prev()
    yield result

iterator reversed_pairs*[T](t:RichNode[T]): (RichNode[T], T) =
  for node in t.reversed_nodes:
    yield (node, node.value)

iterator reversed_values*[T](t:RichNode[T]): T =
  for node in t.reversed_nodes:
    yield node.value

proc toSeq*[T](t:RichNode[T]): seq[T] =
  result = @[]
  for value in t.values:
    result.add value

proc deepStr*[T](t:RichNode[T]):string =
  if t == nil:
    return ""
  result = "(" & deepStr(t.lc) & $t.value & deepStr(t.rc) & ")"

proc `$`*[T](t:RichNode[T]):string =
  if t == nil:
    return "RichNode()"
  result = "RichNode" & deepStr(t)

proc merge*[T](s,t: var RichNode[T]):RichNode[T] =
  if s == nil:
    return t
  if t == nil:
    return s
  # when BST: assert ( not(t.head.value < s.tail.value) )
  if rand(s.len + t.len) < s.len:
    let u = merge(s.rc, t)
    s.replace_rc_of_root(u)
    return s
  else:
    let u = merge(s, t.lc)
    t.replace_lc_of_root(u)
    return t

proc split*[T](u: var RichNode[T], k:int):(RichNode[T],RichNode[T]) =
  if u == nil:
    return (nil,nil)
  if k <= u.lc.len:
    let (s,t) = split(u.lc, k)
    u.replace_lc_of_root(t)
    return (s, u)
  else:
    let (s,t) = split(u.rc, k - u.lc.len - 1)
    u.replace_rc_of_root(s)
    return (u, t)

proc insert*[T](u: var RichNode[T], k:int, x:T):RichNode[T] =
  var (s,t) = u.split(k)
  var c = newRichNode[T](x)
  result = s.merge(c)
  result = result.merge(t)

proc pop*[T](u: var RichNode[T], k:int): (RichNode[T], RichNode[T]) {.discardable.}=
  var (s,ct) = u.split(k)
  var (c,t) = ct.split(1)
  return ( s.merge(t), c)

proc buildRichNode*[T](values:seq[T],l,r:int):RichNode[T] =
  if l == r:
    return nil
  if l+1 == r:
    return newRichNode(values[l])
  let m = (l+r) shr 1
  var s = buildRichNode(values,l,m)
  var t = buildRichNode(values,m,r)
  return merge(s,t)


### {.push. only for BST}
proc lower_bound*[T](u: RichNode[T], x:T):int =
  if u == nil:
    return 0
  if bstOrderRelation(u.value, x):
    return lower_bound(u.rc, x) + u.lc.len + 1
  else:
    return lower_bound(u.lc, x)

proc upper_bound*[T](u: RichNode[T], x:T):int =
  if u == nil:
    return 0
  if bstOrderRelation(x, u.value):
    return upper_bound(u.lc, x)
  else:
    return upper_bound(u.rc, x) + u.lc.len + 1

proc index*[T](u: RichNode[T], x:T):int = #iru?
  let l = u.lower_bound(x)
  let r = u.upper_bound(x)
  if l == r:
    return -1
  return l

proc count*[T](u: RichNode[T], x:T):int = #iru?
  u.upper_bound(x) - u.lower_bound(x)

proc find*[T](u:RichNode[T], x:T): RichNode[T] =
  # upper_bound wo consistently ni tukurenai node koredake
  if u == nil:
    return nil
  if bstOrderRelation(x, u.value):
    return u.lc.find(x)
  elif bstOrderRelation(u.value, x):
    return u.rc.find(x)
  else:
    return u

proc contains*[T](u:RichNode[T], x:T):bool = #iru?
  # can be used as "v in bst"
  u.find(x) != nil

proc incl*[T](u: var RichNode[T], x:T):RichNode[T] = #iru?
  let k = u.upper_bound(x)
  u.insert(k,x)

proc excl*[T](u: var RichNode[T], x:T):(RichNode[T],RichNode[T]) = #iru?
  let k = u.index(x)
  if k == -1:
    return (u,nil)
  u.pop(k)
### {.pop. only for BST}


### {.push. only for BIT}
proc order_query*[T](u: RichNode[T], d:int, l,r:int): T =
  if l == 0 and u.len == r:
    return u.order_bests[d]
  result = bitOrderWorsts[d]
  if l < u.lc.len:
    let temp = u.lc.order_query(d, l, min(u.lc.len,r))
    if bitOrderRelations[d](temp, result):
      result = temp
  if l <= u.lc.len and u.lc.len+1 <= r:
    let temp = u.value
    if bitOrderRelations[d](temp, result):
      result = temp
  if u.lc.len+1 < r:
    let temp = u.rc.order_query(d, max(0,l-(u.lc.len+1)), r-(u.lc.len+1))
    if bitOrderRelations[d](temp, result):
      result = temp

proc find_best*[T](u:RichNode[T], d:int): RichNode[T] =
  var best_value = u.value
  var best_came_from = 0
  if u.lc != nil and bitOrderRelations[d](u.lc.order_bests[d],best_value):
    best_value = u.lc.order_bests[d]
    best_came_from = -1
  if u.rc != nil and bitOrderRelations[d](u.rc.order_bests[d],best_value):
    best_value = u.rc.order_bests[d]
    best_came_from = 1
  if best_came_from == -1:
    return u.lc.find_best(d)
  elif best_came_from == 1:
    return u.rc.find_best(d)
  else:
    return u

proc index_best*[T](u:RichNode[T], d:int): int =
  var best_value = u.value
  var best_came_from = 0
  if u.lc != nil and bitOrderRelations[d](u.lc.order_bests[d],best_value):
    best_value = u.lc.order_bests[d]
    best_came_from = -1
  if u.rc != nil and bitOrderRelations[d](u.rc.order_bests[d],best_value):
    best_value = u.rc.order_bests[d]
    best_came_from = 1
  if best_came_from == -1:
    return u.lc.index_best(d)
  elif best_came_from == 1:
    return u.rc.index_best(d)+u.lc.len+1
  else:
    return u.lc.len
### {.pop. only for BIT}




type Rich*[T] = object
  root: RichNode[T]

proc buildRich*[T](values:seq[T]):Rich[T] =
  result = Rich[T](root: buildRichNode(values,0,values.len))

proc newRich*[T]():Rich[T] =
  result = Rich[T](root:nil)

proc newRich*[T](values:seq[T]):Rich[T] = buildRich(values)

proc newRichBST*[T]():Rich[T] =
  result = Rich[T](root:nil)

proc newRichBST*[T](values:seq[T]):Rich[T] =
  result = newRich[T]()
  for value in values:
    result.incl(value)

proc head*[T](rich:Rich[T]):RichNode[T] = rich.root.head()
proc tail*[T](rich:Rich[T]):RichNode[T] = rich.root.tail()
proc len*[T](rich:Rich[T]):int = rich.root.len
proc `[]`*[T](rich:Rich[T],k:int):RichNode[T] = rich.root[k]
proc `[]=`*[T](rich:var Rich[T],k:int,x:T) = rich.root[k] = x

iterator nodes*[T](rich:Rich[T]): RichNode[T] =
  if rich.len != 0:
    var result = rich.head()
    while result != nil:
      yield result
      result = result.next()

iterator pairs*[T](rich:Rich[T]): (RichNode[T], T) =
  # can be used as "for k,v in rich:"
  for node in rich.nodes:
    yield (node, node.value)

iterator values*[T](rich:Rich[T]): T =
  for node in rich.nodes:
    yield node.value

iterator items*[T](rich:Rich[T]): RichNode[T] =
  # can be used as "for k in rich:"
  for node in rich.nodes:
    yield node

iterator reversed_nodes*[T](rich:Rich[T]): RichNode[T] =
  var result = rich.tail()
  while result != nil:
    yield result
    result = result.prev()

iterator reversed_pairs*[T](rich:Rich[T]): (RichNode[T], T) =
  for node in rich.reversed_nodes:
    yield (node, node.value)

iterator reversed_values*[T](rich:Rich[T]): T =
  for node in rich.reversed_nodes:
    yield node.value

proc toSeq*[T](rich:Rich[T]): seq[T] =
  result = @[]
  for value in rich.values:
    result.add value

proc `$`*[T](rich:Rich[T]):string = "Rich" & deepStr(rich.root)

proc merge*[T](s,t:Rich[T]):Rich[T] =
  var s_root = s.root
  var t_root = t.root
  Rich[T](root:merge(s_root, t_root))

proc split*[T](u:Rich[T], k:int):(Rich[T],Rich[T]) =
  var u_root = u.root
  let (s_root,t_root) = u_root.split(k)
  return ( Rich[T](root:s_root), Rich[T](root:t_root) )

proc insert*[T](rich: var Rich[T], k:int, x:T) =
  rich.root = rich.root.insert(k,x)

proc pop*[T](rich: var Rich[T], k:int):T {.discardable.}=
  let (new_root,c) = rich.root.pop(k)
  rich.root = new_root
  return c.value


### {.push. common for List}
proc peek*[T](u: Rich[T], k:int):T = u[k].value
proc push_front*[T](u: var Rich[T], x:T) = u.insert(0,x)
proc push_back*[T](u: var Rich[T], x:T) = u.insert(u.len,x)
proc peek_front*[T](u: Rich[T]):T = u.peek(0)
proc peek_back*[T](u: Rich[T]):T = u.peek(u.len-1)
proc pop_front*[T](u: var Rich[T]):T {.discardable.} = u.pop(0)
proc pop_back*[T](u: var Rich[T]):T {.discardable.} = u.pop(u.len-1)
### {.pop. common for List}


### {.push. only for BST}
proc lower_bound*[T](bst: Rich[T], x:T):int = bst.root.lower_bound(x)
proc upper_bound*[T](bst: Rich[T], x:T):int = bst.root.upper_bound(x)
proc index*[T](bst: Rich[T], x:T):int = bst.root.index(x)
proc count*[T](bst: Rich[T], x:T):int = bst.root.count(x)
proc find*[T](bst:Rich[T], x:T):RichNode[T] = bst.root.find(x)
proc contains*[T](bst:Rich[T], x:T):bool = bst.root.contains(x)

proc incl*[T](bst: var Rich[T], x:T) =
  if bst.root == nil:
    bst.root = newRichNode[T](x)
    return
  bst.root = bst.root.incl(x)

proc containsOrIncl*[T](bst: var Rich[T], x:T):bool {.discardable.} =
  result = bst.contains(x)
  if not result:
    bst.incl(x)

proc excl*[T](bst: var Rich[T], x:T):bool {.discardable.} =
  let (new_root,c) = bst.root.excl(x)
  bst.root = new_root
  return c != nil

proc union*[T](s,t: Rich[T]):Rich[T] =
  var u_vals = newSeq[T]()
  var s_node = s.head()
  var t_node = t.head()
  while s_node != nil or t_node != nil:
    if t_node == nil or (s_node != nil and bstOrderRelation(s_node.value, t_node.value)):
      u_vals.add s_node.value
      s_node = s_node.next()
    else:
      u_vals.add t_node.value
      t_node = t_node.next()
  return newRich(u_vals)

proc intersection*[T](s,t: Rich[T]):Rich[T] =
  var u_vals = newSeq[T]()
  var s_node = s.head()
  var t_node = t.head()
  while s_node != nil and t_node != nil:
    if s_node.value == t_node.value:
      u_vals.add s_node.value
      s_node = s_node.next()
      t_node = t_node.next()
    elif bstOrderRelation(s_node.value, t_node.value):
      s_node = s_node.next()
    else:
      t_node = t_node.next()
  return newRich(u_vals)
### {.pop. only for BST}


### {.push. only for BIT}
proc order_query*[T](rich: Rich[T], args:varargs[int]): T =
  # args == () or (d,) or (l,r) or (d,l,r)
  # When bitOrderOps[d] == `<`:
  #   min(rich[l..<r])
  var d,l,r:int
  if args.len >= 3:
    (d,l,r) = (args[0], args[1], args[2])
  elif args.len == 2:
    (d,l,r) = (0, args[0], args[1])
  elif args.len == 1:
    (d,l,r) = (args[0], 0, rich.len)
  else:
    (d,l,r) = (0, 0, rich.len)
  rich.root.order_query(d,l,r)

proc find_best*[T](rich:Rich[T], d:int=0): RichNode[T] = rich.root.find_best(d)
proc index_best*[T](rich:Rich[T], d:int=0): int = rich.root.index_best(d)
proc peek_best*[T](rich:Rich[T], d:int=0): T = rich.root.order_bests[d]
proc pop_best*[T](rich:var Rich[T], d:int=0): T {.discardable.} = rich.pop(rich.index_best(d))
### {.pop. only for BIT}

# -------------------------------------------------- #



let (N,M) = input(int,2)
type LRC = tuple
  l:int
  r:int
  c:int
proc cmp(x,y:LRC):int =
  result = cmp(x.l,y.l)
  if result!=0: return result
  result = cmp(x.r,y.r)
  if result!=0: return result
  return cmp(x.c,y.c)


var lrcs = newSeq[LRC]()
for _ in M:
  var (l,r,c) = input(int,3)
  l -= 1
  r -= 1
  lrcs.add( (l,r,c) )

lrcs.sort(cmp)





var kouhos = newRich[Kouho]() # po ascending, cost ascending
kouhos.push_back( (0,0) )

for lrc in lrcs:
  let (l,r,c) = lrc
  while kouhos.peek_front.po < l:
    kouhos.pop_front()
    if kouhos.len == 0:
      echo -1
      quit()

  let new_po = r
  let new_cost = kouhos.peek_front.cost + c
  let new_kouho = (new_po, new_cost)

  myDump kouhos
  myDump new_kouho
  let fun = kouhos.upper_bound(new_kouho)
  myDump "fun",fun
  var doko = fun-1
  while doko>=0:
    if kouhos[doko].value.cost >= new_cost:
      kouhos.pop(doko)
    else:
      break
    doko -= 1
  myDump "doko",doko
  if doko!= -1 and kouhos[doko].value.po == new_po and kouhos[doko].value.cost <= new_cost:
    discard
  else:
    kouhos.insert(doko+1,new_kouho)

myDump kouhos


for v in kouhos.values:
  if v.po == N-1:
    echo v.cost
    quit()

echo -1
quit()