C. The Hard Work of Paparazzi

problem_index: C

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
Explanation of the first testcase: There is only one celebrity in the city, and he will be at intersection $$$(6,8)$$$ exactly $$$11$$$ minutes after the beginning of the working day. Since you are initially at $$$(1,1)$$$ and you need $$$|1-6|+|1-8|=5+7=12$$$ minutes to reach $$$(6,8)$$$ you cannot take a photo of the celebrity. Thus you cannot get any photo and the answer is $$$0$$$.
Explanation of the second testcase: One way to take $$$4$$$ photos (which is the maximum possible) is to take photos of celebrities with indexes $$$3, 5, 7, 9$$$ (see the image for a visualization of the strategy):
To move from the office at $$$(1,1)$$$ to the intersection $$$(5,5)$$$ you need $$$|1-5|+|1-5|=4+4=8$$$ minutes, so you arrive at minute $$$8$$$ and you are just in time to take a photo of celebrity $$$3$$$.  Then, just after you have taken a photo of celebrity $$$3$$$, you move toward the intersection $$$(4,4)$$$. You need $$$|5-4|+|5-4|=1+1=2$$$ minutes to go there, so you arrive at minute $$$8+2=10$$$ and you wait until minute $$$12$$$, when celebrity $$$5$$$ appears.  Then, just after you have taken a photo of celebrity $$$5$$$, you go to the intersection $$$(6,6)$$$. You need $$$|4-6|+|4-6|=2+2=4$$$ minutes to go there, so you arrive at minute $$$12+4=16$$$ and you wait until minute $$$17$$$, when celebrity $$$7$$$ appears.  Then, just after you have taken a photo of celebrity $$$7$$$, you go to the intersection $$$(5,4)$$$. You need $$$|6-5|+|6-4|=1+2=3$$$ minutes to go there, so you arrive at minute $$$17+3=20$$$ and you wait until minute $$$21$$$ to take a photo of celebrity $$$9$$$.
![image](images/cf_1427_C/1.png)
Explanation of the third testcase: The only way to take $$$1$$$ photo (which is the maximum possible) is to take a photo of the celebrity with index $$$1$$$ (since $$$|2-1|+|1-1|=1$$$, you can be at intersection $$$(2,1)$$$ after exactly one minute, hence you are just in time to take a photo of celebrity $$$1$$$).
Explanation of the fourth testcase: One way to take $$$3$$$ photos (which is the maximum possible) is to take photos of celebrities with indexes $$$3, 8, 10$$$:
To move from the office at $$$(1,1)$$$ to the intersection $$$(101,145)$$$ you need $$$|1-101|+|1-145|=100+144=244$$$ minutes, so you can manage to be there when the celebrity $$$3$$$ appears (at minute $$$341$$$).  Then, just after you have taken a photo of celebrity $$$3$$$, you move toward the intersection $$$(149,379)$$$. You need $$$|101-149|+|145-379|=282$$$ minutes to go there, so you arrive at minute $$$341+282=623$$$ and you wait until minute $$$682$$$, when celebrity $$$8$$$ appears.  Then, just after you have taken a photo of celebrity $$$8$$$, you go to the intersection $$$(157,386)$$$. You need $$$|149-157|+|379-386|=8+7=15$$$ minutes to go there, so you arrive at minute $$$682+15=697$$$ and you wait until minute $$$855$$$ to take a photo of celebrity $$$10$$$.

solutions: ["import os\nimport sys\nimport math\nfrom io import BytesIO, IOBase\nfrom fractions import Fraction\nimport collections\nfrom itertools import permutations\nfrom collections import defaultdict\nfrom collections import deque\nimport threading\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\nclass SegmentTree:\n\n\tdef __init__(self, data, default=-10 ** 6, func=lambda a, b: max(a, b)):\n\t\tself._default = default\n\t\tself._func = func\n\t\tself._len = len(data)\n\t\tself._size = _size = 1 << (self._len - 1).bit_length()\n\t\tself.data = [default] * (2 * _size)\n\t\tself.data[_size:_size + self._len] = data\n\t\tfor i in reversed(range(_size)):\n\t\t\tself.data[i] = func(self.data[i + i], self.data[i + i + 1])\n\n\tdef __delitem__(self, idx):\n\t\tself[idx] = self._default\n\n\tdef __getitem__(self, idx):\n\t\treturn self.data[idx + self._size]\n\n\tdef __setitem__(self, idx, value):\n\t\tidx += self._size\n\t\tself.data[idx] = value\n\t\tidx >>= 1\n\t\twhile idx:\n\t\t\tself.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])\n\t\t\tidx >>= 1\n\n\tdef __len__(self):\n\t\treturn self._len\n\n\tdef query(self, start, stop):\n\t\tif start == stop:\n\t\t\treturn self.__getitem__(start)\n\t\tstop += 1\n\t\tstart += self._size\n\t\tstop += self._size\n\t\tres = self._default\n\t\twhile start < stop:\n\t\t\tif start & 1:\n\t\t\t\tres = self._func(res, self.data[start])\n\t\t\t\tstart += 1\n\t\t\tif stop & 1:\n\t\t\t\tstop -= 1\n\t\t\t\tres = self._func(res, self.data[stop])\n\t\t\tstart >>= 1\n\t\t\tstop >>= 1\n\t\treturn res\n\n\tdef __repr__(self):\n\t\treturn 'SegmentTree({0})'.format(self.data)\n\nclass SegmentTree1:\n\n\tdef __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):\n\t\tself._default = default\n\t\tself._func = func\n\t\tself._len = len(data)\n\t\tself._size = _size = 1 << (self._len - 1).bit_length()\n\t\tself.data = [default] * (2 * _size)\n\t\tself.data[_size:_size + self._len] = data\n\t\tfor i in reversed(range(_size)):\n\t\t\tself.data[i] = func(self.data[i + i], self.data[i + i + 1])\n\n\tdef __delitem__(self, idx):\n\t\tself[idx] = self._default\n\n\tdef __getitem__(self, idx):\n\t\treturn self.data[idx + self._size]\n\n\tdef __setitem__(self, idx, value):\n\t\tidx += self._size\n\t\tself.data[idx] = value\n\t\tidx >>= 1\n\t\twhile idx:\n\t\t\tself.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])\n\t\t\tidx >>= 1\n\n\tdef __len__(self):\n\t\treturn self._len\n\n\tdef query(self, start, stop):\n\t\tif start == stop:\n\t\t\treturn self.__getitem__(start)\n\t\tstop += 1\n\t\tstart += self._size\n\t\tstop += self._size\n\t\tres = self._default\n\t\twhile start < stop:\n\t\t\tif start & 1:\n\t\t\t\tres = self._func(res, self.data[start])\n\t\t\t\tstart += 1\n\t\t\tif stop & 1:\n\t\t\t\tstop -= 1\n\t\t\t\tres = self._func(res, self.data[stop])\n\t\t\tstart >>= 1\n\t\t\tstop >>= 1\n\t\treturn res\n\n\tdef __repr__(self):\n\t\treturn 'SegmentTree({0})'.format(self.data)\nMOD = 10 ** 9 + 7\n\nclass Factorial:\n\n\tdef __init__(self, MOD):\n\t\tself.MOD = MOD\n\t\tself.factorials = [1, 1]\n\t\tself.invModulos = [0, 1]\n\t\tself.invFactorial_ = [1, 1]\n\n\tdef calc(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate n!')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tif n < len(self.factorials):\n\t\t\treturn self.factorials[n]\n\t\tnextArr = [0] * (n + 1 - len(self.factorials))\n\t\tinitialI = len(self.factorials)\n\t\tprev = self.factorials[-1]\n\t\tm = self.MOD\n\t\tfor i in range(initialI, n + 1):\n\t\t\tprev = nextArr[i - initialI] = prev * i % m\n\t\tself.factorials += nextArr\n\t\treturn self.factorials[n]\n\n\tdef inv(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate n^(-1)')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tp = self.MOD\n\t\tpi = n % p\n\t\tif pi < len(self.invModulos):\n\t\t\treturn self.invModulos[pi]\n\t\tnextArr = [0] * (n + 1 - len(self.invModulos))\n\t\tinitialI = len(self.invModulos)\n\t\tfor i in range(initialI, min(p, n + 1)):\n\t\t\tnext = -self.invModulos[p % i] * (p // i) % p\n\t\t\tself.invModulos.append(next)\n\t\treturn self.invModulos[pi]\n\n\tdef invFactorial(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate (n^(-1))!')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tif n < len(self.invFactorial_):\n\t\t\treturn self.invFactorial_[n]\n\t\tself.inv(n)\n\t\tnextArr = [0] * (n + 1 - len(self.invFactorial_))\n\t\tinitialI = len(self.invFactorial_)\n\t\tprev = self.invFactorial_[-1]\n\t\tp = self.MOD\n\t\tfor i in range(initialI, n + 1):\n\t\t\tprev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p\n\t\tself.invFactorial_ += nextArr\n\t\treturn self.invFactorial_[n]\n\nclass Combination:\n\n\tdef __init__(self, MOD):\n\t\tself.MOD = MOD\n\t\tself.factorial = Factorial(MOD)\n\n\tdef ncr(self, n, k):\n\t\tif k < 0 or n < k:\n\t\t\treturn 0\n\t\tk = min(k, n - k)\n\t\tf = self.factorial\n\t\treturn f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD\nmod = 10 ** 9 + 7\nomod = 998244353\nprime = [True for i in range(200001)]\npp = [0] * 200001\n\ndef SieveOfEratosthenes(n=200000):\n\tp = 2\n\twhile p * p <= n:\n\t\tif prime[p] == True:\n\t\t\tfor i in range(p * p, n + 1, p):\n\t\t\t\tprime[i] = False\n\t\tp += 1\n(r, n) = map(int, input().split())\nM = 2 * r\nA = [(0, 1, 1)] + [tuple(map(int, input().split())) for _ in range(n)]\nDP = [-n] * (n + 1)\nDP[0] = 0\nii = 0\nbesti = -n\nfor i in range(1, n + 1):\n\t(t, x, y) = A[i]\n\twhile A[ii][0] + M <= t:\n\t\tbesti = max(besti, DP[ii])\n\t\tii += 1\n\tb = besti + 1\n\tj = i\n\twhile j > 0:\n\t\tj -= 1\n\t\t(to, xo, yo) = A[j]\n\t\tif DP[j] >= b and abs(xo - x) + abs(yo - y) <= t - to:\n\t\t\tb = DP[j] + 1\n\t\tif t - to >= M:\n\t\t\tbreak\n\tDP[i] = b\nprint(max(DP))\n", "import sys\ninput = sys.stdin.readline\n(r, n) = map(int, input().split())\nM = 2 * r\nA = [(0, 1, 1)] + [tuple(map(int, input().split())) for _ in range(n)]\nDP = [-n] * (n + 1)\nDP[0] = 0\nii = 0\nbesti = -n\nfor i in range(1, n + 1):\n\t(t, x, y) = A[i]\n\twhile A[ii][0] + M <= t:\n\t\tbesti = max(besti, DP[ii])\n\t\tii += 1\n\tb = besti + 1\n\tj = i\n\twhile j > 0:\n\t\tj -= 1\n\t\t(to, xo, yo) = A[j]\n\t\tif DP[j] >= b and abs(xo - x) + abs(yo - y) <= t - to:\n\t\t\tb = DP[j] + 1\n\t\tif t - to >= M:\n\t\t\tbreak\n\tDP[i] = b\nprint(max(DP))\n", "import os, sys, atexit\nfrom io import BytesIO\nsys.stdout = BytesIO()\n_write = sys.stdout.write\nsys.stdout.write = lambda s: _write(s.encode())\natexit.register(lambda : os.write(1, sys.stdout.getvalue()))\ninput = BytesIO(os.read(0, os.fstat(0).st_size)).readline\n(r, n) = map(int, input().split())\na = [[0, 1, 1]] + [list(map(int, input().split())) for _ in range(n)]\nmem = [0] * (n + 1)\nma = [0] * (n + 1)\nfor (i, (t, x, y)) in enumerate(a[1:], 1):\n\tix = i - 1\n\tcur = -(1 << 25)\n\twhile ix > -1:\n\t\t(t1, x1, y1) = a[ix]\n\t\tif mem[ix] > cur and abs(x - x1) + abs(y - y1) <= t - t1:\n\t\t\tcur = mem[ix]\n\t\tif a[ix][0] <= t - 1000:\n\t\t\tif ma[ix] > cur:\n\t\t\t\tcur = ma[ix]\n\t\t\tbreak\n\t\tix -= 1\n\tmem[i] = cur + 1\n\tma[i] = max(ma[i - 1], mem[i])\nprint(ma[-1])\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nfrom types import GeneratorType\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\timport os\n\t\tself.os = os\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tself.os.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nimport time\nstart_time = time.time()\nimport collections as col\nimport math\nfrom functools import reduce\n\ndef getInts():\n\treturn [int(s) for s in input().split()]\n\ndef getInt():\n\treturn int(input())\n\ndef getStrs():\n\treturn [s for s in input().split()]\n\ndef getStr():\n\treturn input()\n\ndef listStr():\n\treturn list(input())\n\ndef solve():\n\t(R, N) = getInts()\n\tdp = [-10 ** 5 - 1] * (N + 1)\n\tA = [(0, 1, 1)] + [tuple(getInts()) for i in range(N)]\n\tmax_dp = [0] * (N + 1)\n\tM = 2 * R\n\tdp[0] = 0\n\tfor i in range(1, N + 1):\n\t\t(t, x, y) = A[i]\n\t\tbest = 0\n\t\tif i >= M:\n\t\t\tdp[i] = max_dp[i - M] + 1\n\t\tbest = dp[i]\n\t\tfor j in range(i - 1, max(-1, i - M), -1):\n\t\t\t(t0, x0, y0) = A[j]\n\t\t\tif dp[j] >= best and abs(x - x0) + abs(y - y0) <= t - t0:\n\t\t\t\tbest = dp[j] + 1\n\t\tdp[i] = best\n\t\tmax_dp[i] = max(max_dp[i - 1], dp[i])\n\treturn max_dp[N]\nprint(solve())\n", "from sys import stdin\n\ndef input0():\n\treturn stdin.readline()\n(r, n) = map(int, input0().split())\npoints = []\nfor i in range(n):\n\tp = list(map(int, input0().split()))\n\tpoints.append(p)\ndp = []\nm = []\nfor i in range(n):\n\tbest = 0\n\tj = i - 1\n\twhile j > -1:\n\t\tif points[i][0] - points[j][0] < 2 * r:\n\t\t\tif dp[j] + 1 > best and dp[j] != 0:\n\t\t\t\tif points[i][0] - points[j][0] >= abs(points[i][1] - points[j][1]) + abs(points[i][2] - points[j][2]):\n\t\t\t\t\tbest = dp[j] + 1\n\t\telse:\n\t\t\tbreak\n\t\tj -= 1\n\tif best == 0 and j == -1:\n\t\tif abs(points[i][1] - 1) + abs(points[i][2] - 1) <= points[i][0]:\n\t\t\tbest = 1\n\tif j >= 0:\n\t\tif m[j] + 1 > best:\n\t\t\tbest = m[j] + 1\n\tif len(m) == 0:\n\t\tm.append(best)\n\telse:\n\t\tm.append(max(best, m[-1]))\n\tdp.append(best)\nprint(max(dp[-1], m[-1]))\n", "import os\nimport io\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\nTC = 1\nfor tc in range(TC):\n\t(R, N) = map(int, input().split())\n\tT = [0 for _ in range(N + 1)]\n\tX = [0 for _ in range(N + 1)]\n\tY = [0 for _ in range(N + 1)]\n\tV = [0 for _ in range(N + 1)]\n\tM = [0 for _ in range(N + 1)]\n\tX[0] = 1\n\tY[0] = 1\n\tresult = 0\n\tfor j in range(1, N + 1):\n\t\t(t, x, y) = map(int, input().split())\n\t\tT[j] = t\n\t\tX[j] = x\n\t\tY[j] = y\n\t\tr = -N\n\t\tfor i in range(j - 1, max(-1, j - 2 * R - 1), -1):\n\t\t\tif t - T[i] >= 2 * R:\n\t\t\t\tr = max(r, M[i] + 1)\n\t\t\t\tbreak\n\t\t\tif V[i] >= r and abs(x - X[i]) + abs(y - Y[i]) <= t - T[i]:\n\t\t\t\tr = max(r, V[i] + 1)\n\t\tV[j] = r\n\t\tM[j] = max(M[j - 1], r)\n\tprint(M[-1])\n", "def main():\n\timport sys\n\tfrom collections import defaultdict\n\tinput = sys.stdin.readline\n\t(r, n) = map(int, input().split())\n\tdic = defaultdict(set)\n\tdic[0].add((0, 1, 1))\n\tans = 0\n\tfor _ in range(n):\n\t\t(t, x, y) = map(int, input().split())\n\t\tf = False\n\t\tfor i in range(ans, -1, -1):\n\t\t\tfor (t_, x_, y_) in dic[i]:\n\t\t\t\tif abs(x - x_) + abs(y - y_) <= t - t_:\n\t\t\t\t\tdic[i + 1].add((t, x, y))\n\t\t\t\t\tif i == ans:\n\t\t\t\t\t\tans += 1\n\t\t\t\t\tf = True\n\t\t\t\t\tbreak\n\t\t\tif f:\n\t\t\t\tbreak\n\tprint(ans)\nmain()\n", "import io\nimport os\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n(R, N) = [int(x) for x in input().split()]\nT = [0]\nX = [1]\nY = [1]\ninf = 1 << 20\ndp = [-inf] * (N + 1)\ndp[0] = 0\nfarMax = -inf\nfarIndex = 0\nfor i in range(1, N + 1):\n\t(t, x, y) = [int(x) for x in input().split()]\n\tT.append(t)\n\tX.append(x)\n\tY.append(y)\n\twhile t - T[farIndex] >= 2 * R:\n\t\tfarMax = max(farMax, dp[farIndex])\n\t\tfarIndex += 1\n\tbest = max(dp[i], farMax)\n\tfor j in range(farIndex, i):\n\t\tif best < dp[j] and t - T[j] >= abs(X[j] - x) + abs(Y[j] - y):\n\t\t\tbest = dp[j]\n\tdp[i] = best + 1\nprint(max(dp))\n", "(n, m) = map(int, input().split())\nA = []\nfor i in range(m):\n\t(t, a, b) = map(int, input().split())\n\tif a - 1 + (b - 1) <= t:\n\t\tw = 0\n\telse:\n\t\tw = -1\n\tfor j in range(len(A) - 1, -1, -1):\n\t\tif A[j][4] <= w:\n\t\t\tbreak\n\t\telif A[j][3] > w:\n\t\t\tif t - A[j][0] >= abs(A[j][1] - a) + abs(A[j][2] - b):\n\t\t\t\tw = A[j][3]\n\tif len(A) == 0:\n\t\tif w >= 0:\n\t\t\tA.append((t, a, b, w + 1, 1))\n\telif w >= 0:\n\t\tA.append((t, a, b, w + 1, max(w + 1, A[-1][-1])))\nif A:\n\tprint(A[-1][-1])\nelse:\n\tprint(0)\n", "import sys\nimport io, os\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n(r, n) = map(int, input().split())\nC = [tuple(map(int, input().split())) for i in range(n)]\nDP = [-1] * n\nMAX = [-1] * n\nfor i in range(n):\n\t(t, x, y) = C[i]\n\tif t >= abs(x - 1) + abs(y - 1):\n\t\tDP[i] = 1\n\tif t > r * 2:\n\t\tMAX[i] = 1\n\t\tbreak\nfor i in range(n):\n\tMAX[i] = max(MAX[i], MAX[i - 1])\n\tplay = max(MAX[i], DP[i])\n\tif play == -1:\n\t\tcontinue\n\t(t0, x0, y0) = C[i]\n\tfor j in range(i + 1, n):\n\t\t(t, x, y) = C[j]\n\t\tif t >= t0 + abs(x - x0) + abs(y - y0):\n\t\t\tDP[j] = max(DP[j], play + 1)\n\t\tif t > t0 + r * 2:\n\t\t\tMAX[j] = play + 1\n\t\t\tbreak\nANS = max(max(MAX), max(DP))\nif ANS == -1:\n\tprint(0)\nelse:\n\tprint(ANS)\n", "import sys\ninput = sys.stdin.readline\n(r, n) = [int(i) for i in input().split()]\nm = 2 * r\ncs = []\nfor _ in range(n):\n\tc = tuple((int(i) for i in input().split()))\n\tif c[1] + c[2] - 2 <= c[0]:\n\t\tcs.append(c)\nif cs:\n\tans = [-1] * n\n\tk = 0\n\tbest = 0\n\tbest2 = 0\n\tfor i in range(len(cs)):\n\t\twhile cs[k][0] + m <= cs[i][0]:\n\t\t\tbest = max(best, ans[k])\n\t\t\tk += 1\n\t\tmax_ans = best\n\t\tprev_i = i - 1\n\t\twhile prev_i >= 0:\n\t\t\tif ans[prev_i] > max_ans and abs(cs[prev_i][1] - cs[i][1]) + abs(cs[prev_i][2] - cs[i][2]) <= cs[i][0] - cs[prev_i][0]:\n\t\t\t\tmax_ans = ans[prev_i]\n\t\t\tprev_i -= 1\n\t\t\tif cs[i][0] - cs[prev_i][0] >= m:\n\t\t\t\tbreak\n\t\tans[i] = max_ans + 1\n\t\tbest2 = max(best2, ans[i])\n\tprint(best2)\nelse:\n\tprint(0)\n", "import sys\nfrom io import BytesIO, IOBase\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\timport os\n\t\tself.os = os\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\t\tself.BUFSIZE = 8192\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tself.os.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\ndef get_int():\n\treturn int(input())\n\ndef get_ints():\n\treturn list(map(int, input().split(' ')))\n\ndef get_int_grid(n):\n\treturn [get_ints() for _ in range(n)]\n\ndef solve_c():\n\t(r, n) = get_ints()\n\tcelebs = [(0, 1, 1)] + [tuple(get_ints()) for _ in range(n)]\n\tdp = [-float('inf')] * (n + 1)\n\tdp[0] = 0\n\tdp_max = [0] * (n + 1)\n\tM = 2 * r\n\tfor idx in range(1, n + 1):\n\t\t(t, x, y) = celebs[idx]\n\t\tm = 0\n\t\tif idx >= M:\n\t\t\tdp[idx] = dp_max[idx - M] + 1\n\t\tm = dp[idx]\n\t\tfor jdx in range(idx - 1, max(-1, idx - M), -1):\n\t\t\t(ta, xa, ya) = celebs[jdx]\n\t\t\tif dp[jdx] >= m and abs(x - xa) + abs(y - ya) <= t - ta:\n\t\t\t\tm = dp[jdx] + 1\n\t\tdp[idx] = m\n\t\tdp_max[idx] = max(dp[idx], dp_max[idx - 1])\n\treturn dp_max[-1]\nprint(solve_c())\n", "from sys import stdin\ninput = stdin.readline\n(r, n) = map(int, input().split())\ninp = [[0, 1, 1]] + [list(map(int, input().split())) for _ in range(n)]\ndp = [0 for _ in range(n + 1)]\nmAx = [0 for _ in range(n + 1)]\nfor i in range(1, n + 1):\n\t(t, x, y) = inp[i]\n\tcurr = -(1 << 30)\n\tfor j in range(i - 1, -1, -1):\n\t\t(tt, xx, yy) = inp[j]\n\t\tif mAx[j] < curr:\n\t\t\tbreak\n\t\tif abs(xx - x) + abs(yy - y) <= t - tt:\n\t\t\tcurr = max(curr, dp[j] + 1)\n\tdp[i] = curr\n\tmAx[i] = max(curr, mAx[i - 1])\nprint(mAx[-1])\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\n(r, n) = map(int, input().split())\nts = [0]\nxs = [1]\nys = [1]\nans = [0]\nmaxans = [0]\n\ndef toolong(i, j):\n\tdis = abs(xs[i] - xs[j]) + abs(ys[i] - ys[j])\n\treturn dis > ts[i] - ts[j]\nfor i in range(1, n + 1):\n\t(t, x, y) = map(int, input().split())\n\tts.append(t)\n\txs.append(x)\n\tys.append(y)\n\tcurans = -int(1000000000.0)\n\tfor j in range(i - 1, -1, -1):\n\t\tif maxans[j] < curans:\n\t\t\tbreak\n\t\tif not toolong(i, j):\n\t\t\tcurans = max(curans, ans[j])\n\tcurans += 1\n\tans.append(curans)\n\tmaxans.append(max(maxans[-1], curans))\nprint(maxans[-1])\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\timport os\n\t\tself.os = os\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tself.os.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n(r, n) = map(int, input().split())\nts = [0]\nxs = [1]\nys = [1]\nans = [0]\nmaxans = [0]\n\ndef toolong(i, j):\n\tdis = abs(xs[i] - xs[j]) + abs(ys[i] - ys[j])\n\treturn dis > ts[i] - ts[j]\nfor i in range(1, n + 1):\n\t(t, x, y) = map(int, input().split())\n\tts.append(t)\n\txs.append(x)\n\tys.append(y)\n\tcurans = -int(1000000000.0)\n\tfor j in range(i - 1, -1, -1):\n\t\tif maxans[j] < curans:\n\t\t\tbreak\n\t\tif not toolong(i, j):\n\t\t\tcurans = max(curans, ans[j])\n\tcurans += 1\n\tans.append(curans)\n\tmaxans.append(max(maxans[-1], curans))\nprint(maxans[-1])\n", "(r, n) = map(int, input().split())\nA = []\nfor i in range(n):\n\t(t, x, y) = map(int, input().split())\n\tif x - 1 + (y - 1) > t:\n\t\tcontinue\n\tw = 0\n\tif len(A) == 0:\n\t\tA.append((t, x, y, w + 1, 1))\n\telse:\n\t\tfor ev in reversed(A):\n\t\t\tif ev[4] <= w:\n\t\t\t\tbreak\n\t\t\telif ev[3] > w and t - ev[0] >= abs(ev[1] - x) + abs(ev[2] - y):\n\t\t\t\tw = ev[3]\n\t\tA.append((t, x, y, w + 1, max(w + 1, A[-1][-1])))\nif A:\n\tprint(A[-1][-1])\nelse:\n\tprint(0)\n", "(r, n) = map(int, input().split())\nts = [0]\nxs = [1]\nys = [1]\nans = [0]\nmaxans = [0]\n\ndef toolong(i, j):\n\tdis = abs(xs[i] - xs[j]) + abs(ys[i] - ys[j])\n\treturn dis > ts[i] - ts[j]\nfor i in range(1, n + 1):\n\t(t, x, y) = map(int, input().split())\n\tts.append(t)\n\txs.append(x)\n\tys.append(y)\n\tcurans = -int(1000000000.0)\n\tfor j in range(i - 1, -1, -1):\n\t\tif maxans[j] < curans:\n\t\t\tbreak\n\t\tif not toolong(i, j):\n\t\t\tcurans = max(curans, ans[j])\n\tcurans += 1\n\tans.append(curans)\n\tmaxans.append(max(maxans[-1], curans))\nprint(maxans[-1])\n", "import io, os\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n(r, n) = map(int, input().split())\nt = [0]\nx = [1]\ny = [1]\ncdp = [0]\ndp = [0]\nfor i in range(1, n + 1):\n\t(ti, xi, yi) = map(int, input().split())\n\tt.append(ti)\n\tx.append(xi)\n\ty.append(yi)\n\tmx = -10 ** 9\n\tfor j in range(i)[::-1]:\n\t\tif cdp[j] < mx:\n\t\t\tbreak\n\t\tif abs(xi - x[j]) + abs(yi - y[j]) <= abs(ti - t[j]):\n\t\t\tmx = max(mx, dp[j])\n\tmx += 1\n\tdp.append(mx)\n\tcdp.append(max(cdp[-1], mx))\nprint(cdp[-1])\n", "import os, io\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\n(r, n) = list(map(int, input().split()))\n(tl, xl, yl) = ([0], [1], [1])\nd = [0]\ndv = [0]\nfor i in range(1, n + 1):\n\t(t, x, y) = list(map(int, input().split()))\n\ttl.append(t)\n\txl.append(x)\n\tyl.append(y)\n\tmv = int(-1000000000.0)\n\tfor j in reversed(range(0, i)):\n\t\tif dv[j] < mv:\n\t\t\tbreak\n\t\tif tl[j] + abs(x - xl[j]) + abs(y - yl[j]) <= t:\n\t\t\tmv = max(mv, d[j])\n\tmv += 1\n\td.append(mv)\n\tdv.append(max(dv[-1], mv))\nprint(dv[-1])\n", "def j\u00f5uab(a, b):\n\treturn a[0] - b[0] >= abs(a[1] - b[1]) + abs(a[2] - b[2])\na = [[[0, 1, 1]]]\nb = int(input().strip().split(' ')[1])\nfor i in range(b):\n\tif a[-1] != []:\n\t\ta.append([])\n\tj = len(a) - 1\n\tc = list(map(int, input().strip().split(' ')))\n\twhile j > 0:\n\t\tfor k in a[j - 1]:\n\t\t\tif j\u00f5uab(c, k):\n\t\t\t\ta[j].append(c)\n\t\t\t\tj = 0\n\t\t\t\tbreak\n\t\tj -= 1\nprint(len(a) - 1) if a[-1] != [] else print(len(a) - 2)\n", "import sys\ninput = sys.stdin.readline\n(r, n) = map(int, input().split())\nm = 2 * r\ncs = [(0, 1, 1)] + [tuple(map(int, input().split())) for _ in range(n)]\nans = [-n] * (n + 1)\nans[0] = 0\nk = 0\nbest = -n\nfor i in range(1, n + 1):\n\t(t, x, y) = cs[i]\n\twhile cs[k][0] + m <= t:\n\t\tbest = max(best, ans[k])\n\t\tk += 1\n\tb = best + 1\n\tj = i\n\twhile j > 0:\n\t\tj -= 1\n\t\t(to, xo, yo) = cs[j]\n\t\tif ans[j] >= b and abs(xo - x) + abs(yo - y) <= t - to:\n\t\t\tb = ans[j] + 1\n\t\tif t - to >= m:\n\t\t\tbreak\n\tans[i] = b\nprint(max(ans))\n", "import sys, io, os\nBUFSIZE = 8192\n\nclass FastIO(io.IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = io.BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(io.IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n\ndef print(*args, **kwargs):\n\t(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))\n\tat_start = True\n\tfor x in args:\n\t\tif not at_start:\n\t\t\tfile.write(sep)\n\t\tfile.write(str(x))\n\t\tat_start = False\n\tfile.write(kwargs.pop('end', '\\n'))\n\tif kwargs.pop('flush', False):\n\t\tfile.flush()\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n(R, N) = map(int, input().split())\nTXY = [[0, 1, 1]] + [list(map(int, input().split())) for _ in range(N)]\ndp = [0] * (N + 1)\nmas = [0] * (N + 1)\nfor (i, (t, x, y)) in enumerate(TXY[1:], 1):\n\tleft = i - 1\n\tma = -(1 << 62)\n\twhile left >= 0:\n\t\t(tl, xl, yl) = TXY[left]\n\t\tdp_left = dp[left]\n\t\tif ma < dp_left and abs(xl - x) + abs(yl - y) <= t - tl:\n\t\t\tma = dp_left\n\t\tif tl < t - 1000:\n\t\t\tif mas[left] > ma:\n\t\t\t\tma = mas[left]\n\t\t\tbreak\n\t\tleft -= 1\n\tdp[i] = ma + 1\n\tmas[i] = max(mas[i - 1], ma + 1)\nprint(mas[-1])\n", "from sys import stdin, stdout, setrecursionlimit\nfrom collections import deque\nimport bisect\nR = lambda : stdin.readline().strip()\nRL = lambda f=None: list(map(f, R().split(' '))) if f else list(R().split(' '))\noutput = lambda x: stdout.write(str(x) + '\\n')\noutput_list = lambda x: output(' '.join(map(str, x)))\n\ndef dist(pos, dest):\n\treturn abs(pos[0] - dest[0]) + abs(pos[1] - dest[1])\n\ndef solve(pos, i, spent, celeb, dic):\n\tif i >= len(celeb):\n\t\treturn 0\n\tif spent in dic:\n\t\treturn dic[spent]\n\tch2 = solve(pos, i + 1, spent, celeb, dic)\n\tif dist(pos, celeb[i][1:]) > celeb[i][0] - spent:\n\t\tch1 = ch2\n\telse:\n\t\tch1 = 1 + solve(celeb[i][1:], i + 1, celeb[i][0], celeb, dic)\n\tdic[spent] = max(ch1, ch2)\n\treturn dic[spent]\n(r, n) = RL(int)\nceleb = []\nmaxi = []\n(tl, xl, yl) = ([0], [1], [1])\nd = [0]\ndv = [0]\nfor i in range(1, n + 1):\n\t(t, x, y) = RL(int)\n\ttl.append(t)\n\txl.append(x)\n\tyl.append(y)\n\tmv = int(-1000000000.0)\n\tfor j in reversed(range(0, i)):\n\t\tif dv[j] < mv:\n\t\t\tbreak\n\t\tif tl[j] + abs(x - xl[j]) + abs(y - yl[j]) <= t:\n\t\t\tmv = max(mv, d[j])\n\tmv += 1\n\td.append(mv)\n\tdv.append(max(dv[-1], mv))\nprint(dv[-1])\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\ndef RL():\n\treturn map(int, sys.stdin.readline().rstrip().split())\n\ndef RLL():\n\treturn list(map(int, sys.stdin.readline().rstrip().split()))\n\ndef N():\n\treturn int(input())\n\ndef print_list(l):\n\tprint(' '.join(map(str, l)))\nimport bisect as bs\nfrom collections import defaultdict as dc\n(r, n) = RL()\ndic = dc(set)\ndic[0].add((0, 1, 1))\nm = 0\nfor _ in range(n):\n\t(t, x, y) = RL()\n\tflag = False\n\tfor last in range(m, -1, -1):\n\t\tfor (tt, xx, yy) in dic[last]:\n\t\t\tif abs(x - xx) + abs(y - yy) <= t - tt:\n\t\t\t\tnow = last + 1\n\t\t\t\tdic[now].add((t, x, y))\n\t\t\t\tif last == m:\n\t\t\t\t\tm += 1\n\t\t\t\tflag = True\n\t\t\t\tbreak\n\t\tif flag:\n\t\t\tbreak\nprint(m)\n", "import sys, os, io\ninput = sys.stdin.readline\n(r, n) = map(int, input().split())\nfrom bisect import *\n(T, X, Y) = ([0] * n, [0] * n, [0] * n)\nfor i in range(n):\n\t(T[i], X[i], Y[i]) = map(int, input().split())\nT = [0] + T\nX = [1] + X\nY = [1] + Y\ndp = [0] + [-float('inf')] * n\ncum_max = [0] * (n + 1)\nfor (i, (t, x, y)) in enumerate(zip(T[1:], X[1:], Y[1:])):\n\tmax_dist = max(x - 1, r - x) + max(y - 1, r - y)\n\tif t - max_dist < 0:\n\t\tind = 0\n\telse:\n\t\tind = bisect_left(T, t - max_dist)\n\t\tdp[i + 1] = cum_max[ind - 1] + 1\n\tfor j in range(i, max(-1, ind - 1), -1):\n\t\tif dp[j] < 0:\n\t\t\tcontinue\n\t\tdist = abs(X[i + 1] - X[j]) + abs(Y[i + 1] - Y[j])\n\t\tif dist <= T[i + 1] - T[j]:\n\t\t\tdp[i + 1] = max(dp[i + 1], dp[j] + 1)\n\t\t\tif dp[i + 1] > cum_max[j]:\n\t\t\t\tbreak\n\tcum_max[i + 1] = max(cum_max[i], dp[i + 1])\nans = max(dp)\nprint(ans)\n"]

difficulty: HARD

source: codeforces

raw_problem:
C. The Hard Work of Paparazzi

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

You are a paparazzi working in Manhattan.

Manhattan has $$$r$$$ south-to-north streets, denoted by numbers $$$1, 2,\ldots, r$$$ in order from west to east, and $$$r$$$ west-to-east streets, denoted by numbers $$$1,2,\ldots,r$$$ in order from south to north. Each of the $$$r$$$ south-to-north streets intersects each of the $$$r$$$ west-to-east streets; the intersection between the $$$x$$$-th south-to-north street and the $$$y$$$-th west-to-east street is denoted by $$$(x, y)$$$. In order to move from the intersection $$$(x,y)$$$ to the intersection $$$(x', y')$$$ you need $$$|x-x'|+|y-y'|$$$ minutes.

You know about the presence of $$$n$$$ celebrities in the city and you want to take photos of as many of them as possible. More precisely, for each $$$i=1,\dots, n$$$, you know that the $$$i$$$-th celebrity will be at the intersection $$$(x_i, y_i)$$$ in exactly $$$t_i$$$ minutes from now (and he will stay there for a very short time, so you may take a photo of him only if at the $$$t_i$$$-th minute from now you are at the intersection $$$(x_i, y_i)$$$). You are very good at your job, so you are able to take photos instantaneously. You know that $$$t_i < t_{i+1}$$$ for any $$$i=1,2,\ldots, n-1$$$.

Currently you are at your office, which is located at the intersection $$$(1, 1)$$$. If you plan your working day optimally, what is the maximum number of celebrities you can take a photo of?

Input

The first line of the input contains two positive integers $$$r, n$$$ ($$$1\le r\le 500$$$, $$$1\le n\le 100,000$$$) – the number of south-to-north/west-to-east streets and the number of celebrities.

Then $$$n$$$ lines follow, each describing the appearance of a celebrity. The $$$i$$$-th of these lines contains $$$3$$$ positive integers $$$t_i, x_i, y_i$$$ ($$$1\le t_i\le 1,000,000$$$, $$$1\le x_i, y_i\le r$$$)  — denoting that the $$$i$$$-th celebrity will appear at the intersection $$$(x_i, y_i)$$$ in $$$t_i$$$ minutes from now.

It is guaranteed that $$$t_i<t_{i+1}$$$ for any $$$i=1,2,\ldots, n-1$$$.

Output

Print a single integer, the maximum number of celebrities you can take a photo of.

Examples

Input

10 1
11 6 8

Output

0

Input

6 9
1 2 6
7 5 1
8 5 5
10 3 1
12 4 4
13 6 2
17 6 6
20 1 4
21 5 4

Output

4

Input

10 4
1 2 1
5 10 9
13 8 8
15 9 9

Output

1

Input

500 10
69 477 122
73 186 235
341 101 145
372 77 497
390 117 440
494 471 37
522 300 498
682 149 379
821 486 359
855 157 386

Output

3

Note

Explanation of the first testcase: There is only one celebrity in the city, and he will be at intersection $$$(6,8)$$$ exactly $$$11$$$ minutes after the beginning of the working day. Since you are initially at $$$(1,1)$$$ and you need $$$|1-6|+|1-8|=5+7=12$$$ minutes to reach $$$(6,8)$$$ you cannot take a photo of the celebrity. Thus you cannot get any photo and the answer is $$$0$$$.

Explanation of the second testcase: One way to take $$$4$$$ photos (which is the maximum possible) is to take photos of celebrities with indexes $$$3, 5, 7, 9$$$ (see the image for a visualization of the strategy):

 To move from the office at $$$(1,1)$$$ to the intersection $$$(5,5)$$$ you need $$$|1-5|+|1-5|=4+4=8$$$ minutes, so you arrive at minute $$$8$$$ and you are just in time to take a photo of celebrity $$$3$$$.

 Then, just after you have taken a photo of celebrity $$$3$$$, you move toward the intersection $$$(4,4)$$$. You need $$$|5-4|+|5-4|=1+1=2$$$ minutes to go there, so you arrive at minute $$$8+2=10$$$ and you wait until minute $$$12$$$, when celebrity $$$5$$$ appears.

 Then, just after you have taken a photo of celebrity $$$5$$$, you go to the intersection $$$(6,6)$$$. You need $$$|4-6|+|4-6|=2+2=4$$$ minutes to go there, so you arrive at minute $$$12+4=16$$$ and you wait until minute $$$17$$$, when celebrity $$$7$$$ appears.

 Then, just after you have taken a photo of celebrity $$$7$$$, you go to the intersection $$$(5,4)$$$. You need $$$|6-5|+|6-4|=1+2=3$$$ minutes to go there, so you arrive at minute $$$17+3=20$$$ and you wait until minute $$$21$$$ to take a photo of celebrity $$$9$$$.

Explanation of the third testcase: The only way to take $$$1$$$ photo (which is the maximum possible) is to take a photo of the celebrity with index $$$1$$$ (since $$$|2-1|+|1-1|=1$$$, you can be at intersection $$$(2,1)$$$ after exactly one minute, hence you are just in time to take a photo of celebrity $$$1$$$).

Explanation of the fourth testcase: One way to take $$$3$$$ photos (which is the maximum possible) is to take photos of celebrities with indexes $$$3, 8, 10$$$:

 To move from the office at $$$(1,1)$$$ to the intersection $$$(101,145)$$$ you need $$$|1-101|+|1-145|=100+144=244$$$ minutes, so you can manage to be there when the celebrity $$$3$$$ appears (at minute $$$341$$$).

 Then, just after you have taken a photo of celebrity $$$3$$$, you move toward the intersection $$$(149,379)$$$. You need $$$|101-149|+|145-379|=282$$$ minutes to go there, so you arrive at minute $$$341+282=623$$$ and you wait until minute $$$682$$$, when celebrity $$$8$$$ appears.

 Then, just after you have taken a photo of celebrity $$$8$$$, you go to the intersection $$$(157,386)$$$. You need $$$|149-157|+|379-386|=8+7=15$$$ minutes to go there, so you arrive at minute $$$682+15=697$$$ and you wait until minute $$$855$$$ to take a photo of celebrity $$$10$$$.

question:
You are a paparazzi working in Manhattan.
Manhattan has $$$r$$$ south-to-north streets, denoted by numbers $$$1, 2,\ldots, r$$$ in order from west to east, and $$$r$$$ west-to-east streets, denoted by numbers $$$1,2,\ldots,r$$$ in order from south to north. Each of the $$$r$$$ south-to-north streets intersects each of the $$$r$$$ west-to-east streets; the intersection between the $$$x$$$-th south-to-north street and the $$$y$$$-th west-to-east street is denoted by $$$(x, y)$$$. In order to move from the intersection $$$(x,y)$$$ to the intersection $$$(x', y')$$$ you need $$$|x-x'|+|y-y'|$$$ minutes.
You know about the presence of $$$n$$$ celebrities in the city and you want to take photos of as many of them as possible. More precisely, for each $$$i=1,\dots, n$$$, you know that the $$$i$$$-th celebrity will be at the intersection $$$(x_i, y_i)$$$ in exactly $$$t_i$$$ minutes from now (and he will stay there for a very short time, so you may take a photo of him only if at the $$$t_i$$$-th minute from now you are at the intersection $$$(x_i, y_i)$$$). You are very good at your job, so you are able to take photos instantaneously. You know that $$$t_i < t_{i+1}$$$ for any $$$i=1,2,\ldots, n-1$$$.
Currently you are at your office, which is located at the intersection $$$(1, 1)$$$. If you plan your working day optimally, what is the maximum number of celebrities you can take a photo of?

Input
The first line of the input contains two positive integers $$$r, n$$$ ($$$1\le r\le 500$$$, $$$1\le n\le 100,000$$$) – the number of south-to-north/west-to-east streets and the number of celebrities.
Then $$$n$$$ lines follow, each describing the appearance of a celebrity. The $$$i$$$-th of these lines contains $$$3$$$ positive integers $$$t_i, x_i, y_i$$$ ($$$1\le t_i\le 1,000,000$$$, $$$1\le x_i, y_i\le r$$$)  — denoting that the $$$i$$$-th celebrity will appear at the intersection $$$(x_i, y_i)$$$ in $$$t_i$$$ minutes from now.
It is guaranteed that $$$t_i<t_{i+1}$$$ for any $$$i=1,2,\ldots, n-1$$$.

Output
Print a single integer, the maximum number of celebrities you can take a photo of.

Examples
Input
10 1
11 6 8

Output
0

Input
6 9
1 2 6
7 5 1
8 5 5
10 3 1
12 4 4
13 6 2
17 6 6
20 1 4
21 5 4

Output
4

Input
10 4
1 2 1
5 10 9
13 8 8
15 9 9

Output
1

Input
500 10
69 477 122
73 186 235
341 101 145
372 77 497
390 117 440
494 471 37
522 300 498
682 149 379
821 486 359
855 157 386

Output
3

Note
Explanation of the first testcase: There is only one celebrity in the city, and he will be at intersection $$$(6,8)$$$ exactly $$$11$$$ minutes after the beginning of the working day. Since you are initially at $$$(1,1)$$$ and you need $$$|1-6|+|1-8|=5+7=12$$$ minutes to reach $$$(6,8)$$$ you cannot take a photo of the celebrity. Thus you cannot get any photo and the answer is $$$0$$$.
Explanation of the second testcase: One way to take $$$4$$$ photos (which is the maximum possible) is to take photos of celebrities with indexes $$$3, 5, 7, 9$$$ (see the image for a visualization of the strategy):
 -  To move from the office at $$$(1,1)$$$ to the intersection $$$(5,5)$$$ you need $$$|1-5|+|1-5|=4+4=8$$$ minutes, so you arrive at minute $$$8$$$ and you are just in time to take a photo of celebrity $$$3$$$. -  Then, just after you have taken a photo of celebrity $$$3$$$, you move toward the intersection $$$(4,4)$$$. You need $$$|5-4|+|5-4|=1+1=2$$$ minutes to go there, so you arrive at minute $$$8+2=10$$$ and you wait until minute $$$12$$$, when celebrity $$$5$$$ appears. -  Then, just after you have taken a photo of celebrity $$$5$$$, you go to the intersection $$$(6,6)$$$. You need $$$|4-6|+|4-6|=2+2=4$$$ minutes to go there, so you arrive at minute $$$12+4=16$$$ and you wait until minute $$$17$$$, when celebrity $$$7$$$ appears. -  Then, just after you have taken a photo of celebrity $$$7$$$, you go to the intersection $$$(5,4)$$$. You need $$$|6-5|+|6-4|=1+2=3$$$ minutes to go there, so you arrive at minute $$$17+3=20$$$ and you wait until minute $$$21$$$ to take a photo of celebrity $$$9$$$.  ![image](1.png) Explanation of the third testcase: The only way to take $$$1$$$ photo (which is the maximum possible) is to take a photo of the celebrity with index $$$1$$$ (since $$$|2-1|+|1-1|=1$$$, you can be at intersection $$$(2,1)$$$ after exactly one minute, hence you are just in time to take a photo of celebrity $$$1$$$).
Explanation of the fourth testcase: One way to take $$$3$$$ photos (which is the maximum possible) is to take photos of celebrities with indexes $$$3, 8, 10$$$:
 -  To move from the office at $$$(1,1)$$$ to the intersection $$$(101,145)$$$ you need $$$|1-101|+|1-145|=100+144=244$$$ minutes, so you can manage to be there when the celebrity $$$3$$$ appears (at minute $$$341$$$). -  Then, just after you have taken a photo of celebrity $$$3$$$, you move toward the intersection $$$(149,379)$$$. You need $$$|101-149|+|145-379|=282$$$ minutes to go there, so you arrive at minute $$$341+282=623$$$ and you wait until minute $$$682$$$, when celebrity $$$8$$$ appears. -  Then, just after you have taken a photo of celebrity $$$8$$$, you go to the intersection $$$(157,386)$$$. You need $$$|149-157|+|379-386|=8+7=15$$$ minutes to go there, so you arrive at minute $$$682+15=697$$$ and you wait until minute $$$855$$$ to take a photo of celebrity $$$10$$$.

skill_types: ['Dynamic programming']

data_split: test


A. Parallel Projection

problem_index: A

time_limit: 1 second

memory_limit: 512 megabytes

solutions: ["t = int(input())\r\nwhile t > 0:\r\n    w,d,h=map(int,input().split())\r\n    a,b,f,g=map(int,input().split())\r\n    rest1=(d-g)+(d-b)\r\n    rest2=(w-a)+(w-f)\r\n    k=min(a+f+abs(b-g)+h,b+g+abs(a-f)+h,rest1+abs(a-f)+h,rest2+abs(b-g)+h)\r\n    print(k)\r\n\r\n\r\n\r\n    t -= 1", "t=int(input())\r\nfor i in range(t):\r\n    w,d,h=map(int,input().split())\r\n    a,b,f,g=map(int,input().split())\r\n    print(min(min(2*d-g-b,g+b)+abs(a-f),min(2*w-a-f,a+f)+abs(g-b))+h)", "for _ in range(int(input())):\r\n    l,b,h=map(int,input().split())\r\n    x1,y1,x2,y2=map(int,input().split())\r\n    z=min(x1,y1,x2,y2,l-x1,l-x2,b-y1,b-y2)\r\n    print(2*z+h+abs(x1-x2)+abs(y1-y2))", "t = int(input())\r\nfor _ in range(t):\r\n    \r\n    w,d,h = list(map(int,input().split()))\r\n    a,b,f,g = list(map(int,input().split()))\r\n    w1 = h+b+g+abs(a-f)\r\n    w2 = (d-g)+h+(d-b)+abs(a-f)\r\n    w3 = f + h + a + abs(b-g)\r\n    w4 = (w-f)+h+(w-a)+abs(b-g)\r\n    li=[]\r\n    li.append(w1)\r\n    li.append(w2)\r\n    li.append(w3)\r\n    li.append(w4)\r\n    \r\n    print(min(li))", "t = int(input())\r\nfor i in range(0,t):\r\n     lst = list(map(str, input().split()))\r\n     lst1 = list(map(str, input().split()))\r\n     w = int(lst[0])\r\n     d = int(lst[1])\r\n     h = int(lst[2])\r\n     a = int(lst1[0])\r\n     b = int(lst1[1])\r\n     f = int(lst1[2])\r\n     g = int(lst1[3])\r\n     k = min(g+b,abs(2*d-g-b))\r\n     r = h+abs(f-a)+k\r\n     q = min(a+f,abs(2*w-a-f))\r\n     l = h+abs(g-b)+q\r\n     print(min(r,l))"]

source: codeforces

raw_problem:
A. Parallel Projection

time limit per test
1 second

memory limit per test
512 megabytes

input
standard input

output
standard output

Vika's house has a room in a shape of a rectangular parallelepiped (also known as a rectangular cuboid). Its floor is a rectangle of size $$$w \times d$$$, and the ceiling is right above at the constant height of $$$h$$$. Let's introduce a coordinate system on the floor so that its corners are at points $$$(0, 0)$$$, $$$(w, 0)$$$, $$$(w, d)$$$, and $$$(0, d)$$$.

A laptop is standing on the floor at point $$$(a, b)$$$. A projector is hanging on the ceiling right above point $$$(f, g)$$$. Vika wants to connect the laptop and the projector with a cable in such a way that the cable always goes along the walls, ceiling, or floor (i. e. does not go inside the cuboid). Additionally, the cable should always run parallel to one of the cuboid's edges (i. e. it can not go diagonally).

What is the minimum length of a cable that can connect the laptop to the projector?
  Illustration for the first test case. One of the optimal ways to put the cable is shown in green.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$w$$$, $$$d$$$, and $$$h$$$ ($$$2 \le w, d, h \le 1000$$$) — the size of the room.

The second line contains four integers $$$a$$$, $$$b$$$, $$$f$$$, $$$g$$$ ($$$0 < a, f < w$$$; $$$0 < b, g < d$$$): the laptop is located on the floor at point $$$(a, b)$$$, while the projector is hanging on the ceiling right above point $$$(f, g)$$$.

Output

For each test case, print a single integer — the minimum length of the cable connecting the laptop and the projector that runs only along the walls, floor, and ceiling parallel to cuboid's edges.

Example

Input

5

55 20 29

23 10 18 3

20 10 5

1 5 2 5

15 15 4

7 13 10 10

2 1000 2

1 1 1 999

10 4 10

7 1 2 1

Output

47
8
14
1002
17

Note

The picture in the statement illustrates the first test case.

question:
Vika's house has a room in a shape of a rectangular parallelepiped (also known as a rectangular cuboid). Its floor is a rectangle of size $$$w \times d$$$, and the ceiling is right above at the constant height of $$$h$$$. Let's introduce a coordinate system on the floor so that its corners are at points $$$(0, 0)$$$, $$$(w, 0)$$$, $$$(w, d)$$$, and $$$(0, d)$$$.
A laptop is standing on the floor at point $$$(a, b)$$$. A projector is hanging on the ceiling right above point $$$(f, g)$$$. Vika wants to connect the laptop and the projector with a cable in such a way that the cable always goes along the walls, ceiling, or floor (i. e. does not go inside the cuboid). Additionally, the cable should always run parallel to one of the cuboid's edges (i. e. it can not go diagonally).
What is the minimum length of a cable that can connect the laptop to the projector?
 ![image](1.png) Illustration for the first test case. One of the optimal ways to put the cable is shown in green.
Input
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains three integers $$$w$$$, $$$d$$$, and $$$h$$$ ($$$2 \le w, d, h \le 1000$$$) — the size of the room.
The second line contains four integers $$$a$$$, $$$b$$$, $$$f$$$, $$$g$$$ ($$$0 < a, f < w$$$; $$$0 < b, g < d$$$): the laptop is located on the floor at point $$$(a, b)$$$, while the projector is hanging on the ceiling right above point $$$(f, g)$$$.

Output
For each test case, print a single integer — the minimum length of the cable connecting the laptop and the projector that runs only along the walls, floor, and ceiling parallel to cuboid's edges.

Example
Input
5
55 20 29
23 10 18 3
20 10 5
1 5 2 5
15 15 4
7 13 10 10
2 1000 2
1 1 1 999
10 4 10
7 1 2 1

Output
47
8
14
1002
17

Note
The picture in the statement illustrates the first test case.

data_split: test


C. Drazil Likes Heap

problem_index: C

time_limit: 1.5 seconds

memory_limit: 256 megabytes

solutions: ["import io, os\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\nT = int(input())\nfor _ in range(T):\n\t(H, G) = map(int, input().split())\n\tA = [0] + list(map(int, input().split()))\n\tN = len(A)\n\ttarget_N = 2 ** G - 1\n\ttarget_ans_len = 2 ** H - 2 ** G\n\tAns = []\n\tRoots = [True] * (N + 1)\n\tidx_Roots = 1\n\twhile True:\n\t\tidx = idx_Roots\n\t\tst = []\n\t\twhile True:\n\t\t\tidx_l = idx << 1\n\t\t\tidx_r = idx_l + 1\n\t\t\tst.append((idx, A[idx]))\n\t\t\tif idx_l >= N or A[idx_l] == A[idx_r] == 0:\n\t\t\t\tA[idx] = 0\n\t\t\t\tbreak\n\t\t\telif A[idx_l] > A[idx_r]:\n\t\t\t\tA[idx] = A[idx_l]\n\t\t\t\tidx = idx_l\n\t\t\telse:\n\t\t\t\tA[idx] = A[idx_r]\n\t\t\t\tidx = idx_r\n\t\tif st[-1][0] <= target_N:\n\t\t\tfor (idx, a) in st:\n\t\t\t\tA[idx] = a\n\t\t\t\tRoots[idx] = False\n\t\t\twhile not Roots[idx_Roots]:\n\t\t\t\tidx_Roots += 1\n\t\telse:\n\t\t\tAns.append(idx_Roots)\n\t\t\tif len(Ans) == target_ans_len:\n\t\t\t\tbreak\n\tprint(sum(A))\n\tprint(' '.join(map(str, Ans)))\n"]

source: codeforces

raw_problem:
C. Drazil Likes Heap

time limit per test
1.5 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Drazil likes heap very much. So he created a problem with heap:

There is a max heap with a height $$$h$$$ implemented on the array. The details of this heap are the following:

This heap contains exactly $$$2^h - 1$$$ distinct positive non-zero integers. All integers are distinct. These numbers are stored in the array $$$a$$$ indexed from $$$1$$$ to $$$2^h-1$$$. For any $$$1 < i < 2^h$$$, $$$a[i] < a[\left \lfloor{\frac{i}{2}}\right \rfloor]$$$.

Now we want to reduce the height of this heap such that the height becomes $$$g$$$ with exactly $$$2^g-1$$$ numbers in heap. To reduce the height, we should perform the following action $$$2^h-2^g$$$ times:

Choose an index $$$i$$$, which contains an element and call the following function $$$f$$$ in index $$$i$$$:

Note that we suppose that if $$$a[i]=0$$$, then index $$$i$$$ don't contain an element.

After all operations, the remaining $$$2^g-1$$$ element must be located in indices from $$$1$$$ to $$$2^g-1$$$. Now Drazil wonders what's the minimum possible sum of the remaining $$$2^g-1$$$ elements. Please find this sum and find a sequence of the function calls to achieve this value.

Input

The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 70\,000$$$): the number of test cases.

Each test case contain two lines. The first line contains two integers $$$h$$$ and $$$g$$$ ($$$1 \leq g < h \leq 20$$$). The second line contains $$$n = 2^h-1$$$ distinct positive integers $$$a[1], a[2], \ldots, a[n]$$$ ($$$1 \leq a[i] < 2^{20}$$$). For all $$$i$$$ from $$$2$$$ to $$$2^h - 1$$$, $$$a[i] < a[\left \lfloor{\frac{i}{2}}\right \rfloor]$$$.

The total sum of $$$n$$$ is less than $$$2^{20}$$$.

Output

For each test case, print two lines.

The first line should contain one integer denoting the minimum sum after reducing the height of heap to $$$g$$$. The second line should contain $$$2^h - 2^g$$$ integers $$$v_1, v_2, \ldots, v_{2^h-2^g}$$$. In $$$i$$$-th operation $$$f(v_i)$$$ should be called.

Example

Input

2
3 2
7 6 3 5 4 2 1
3 2
7 6 5 4 3 2 1

Output

10
3 2 3 1
8
2 1 3 1

question:
Drazil likes heap very much. So he created a problem with heap:
There is a max heap with a height $$$h$$$ implemented on the array. The details of this heap are the following:
This heap contains exactly $$$2^h - 1$$$ distinct positive non-zero integers. All integers are distinct. These numbers are stored in the array $$$a$$$ indexed from $$$1$$$ to $$$2^h-1$$$. For any $$$1 < i < 2^h$$$, $$$a[i] < a[\left \lfloor{\frac{i}{2}}\right \rfloor]$$$.
Now we want to reduce the height of this heap such that the height becomes $$$g$$$ with exactly $$$2^g-1$$$ numbers in heap. To reduce the height, we should perform the following action $$$2^h-2^g$$$ times:
Choose an index $$$i$$$, which contains an element and call the following function $$$f$$$ in index $$$i$$$:
![image](1.png)
Note that we suppose that if $$$a[i]=0$$$, then index $$$i$$$ don't contain an element.
After all operations, the remaining $$$2^g-1$$$ element must be located in indices from $$$1$$$ to $$$2^g-1$$$. Now Drazil wonders what's the minimum possible sum of the remaining $$$2^g-1$$$ elements. Please find this sum and find a sequence of the function calls to achieve this value.

Input
The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 70\,000$$$): the number of test cases.
Each test case contain two lines. The first line contains two integers $$$h$$$ and $$$g$$$ ($$$1 \leq g < h \leq 20$$$). The second line contains $$$n = 2^h-1$$$ distinct positive integers $$$a[1], a[2], \ldots, a[n]$$$ ($$$1 \leq a[i] < 2^{20}$$$). For all $$$i$$$ from $$$2$$$ to $$$2^h - 1$$$, $$$a[i] < a[\left \lfloor{\frac{i}{2}}\right \rfloor]$$$.
The total sum of $$$n$$$ is less than $$$2^{20}$$$.

Output
For each test case, print two lines.
The first line should contain one integer denoting the minimum sum after reducing the height of heap to $$$g$$$. The second line should contain $$$2^h - 2^g$$$ integers $$$v_1, v_2, \ldots, v_{2^h-2^g}$$$. In $$$i$$$-th operation $$$f(v_i)$$$ should be called.

Example
Input
2
3 2
7 6 3 5 4 2 1
3 2
7 6 5 4 3 2 1

Output
10
3 2 3 1
8
2 1 3 1

tags: ['Greedy algorithms', 'Data structures', 'Implementation', 'Constructive algorithms']

skill_types: ['Data structures', 'Greedy algorithms']

raw_tags: ['data structures', 'greedy', 'implementation', 'constructive algorithms']

data_split: test