B. Views Matter

problem_index: B

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
The following pictures illustrate the first example and its possible solution.
Blue cells indicate removed blocks. There are $$$10$$$ blue cells, so the answer is $$$10$$$.
![image](images/cf_1061_B/2.png)

solutions: ["def solve(xs):\n\tif len(xs) == 1:\n\t\treturn 0\n\theights = sorted(xs)[::-1]\n\tused = 0\n\tneeded = heights[0]\n\tfor i in range(len(heights)):\n\t\tcurrent = heights[i]\n\t\tif needed <= current:\n\t\t\tused += 1\n\t\t\tneeded -= 1\n\t\telse:\n\t\t\tused += needed - current\n\t\t\tused += 1\n\t\t\tneeded = current - 1\n\tif needed > 0:\n\t\tused += needed\n\treturn sum(xs) - used\n(n, m) = map(int, input().split())\nxs = list(map(int, input().split()))[:n]\nprint(solve(xs))\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.sort()\ntemp = 1\ntop = 0\nside = 0\ntotal = sum(a)\nfor i in range(n):\n\tif i == 0:\n\t\ttop += 1\n\t\tside += 1\n\t\ttotal -= 1\n\telif a[i] == temp:\n\t\ttop += 1\n\t\ttotal -= 1\n\telif a[i] > temp:\n\t\tside += 1\n\t\ttop += 1\n\t\ttemp += 1\n\t\ttotal -= 1\nif side < a[n - 1]:\n\ttotal -= a[n - 1] - side\nif n == 1:\n\tprint(0)\nelse:\n\tprint(total)\n", "(n, m) = [int(x) for x in input().split()]\na = [int(x) for x in input().split()]\ns = sum(a)\nneed = 0\na.sort()\nj = 1\nflag = 0\nk = max(a)\nif n == 1:\n\tprint(0)\nelse:\n\tfor i in range(n):\n\t\tif a[i] < j:\n\t\t\tflag = 1\n\t\telse:\n\t\t\tflag = 0\n\t\tif a[i] == 1:\n\t\t\tneed += 1\n\t\telif a[i] >= j and i != n - 1:\n\t\t\tneed += 1\n\t\telif a[i] >= j and i == n - 1 and (j <= k):\n\t\t\tneed += k - j + 1\n\t\telse:\n\t\t\tneed += 1\n\t\tif flag != 1:\n\t\t\tj += 1\n\tprint(s - need)\n", "(n, m) = map(int, input().split())\na = sorted([int(x) for x in input().split()])\ntotal = 0\nm = max(a)\nfor i in range(n):\n\tif a[i] > total:\n\t\ttotal += 1\nprint(sum(a) - n - m + total)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.sort()\nx = n\nh = 0\nfor i in range(n):\n\tif a[i] > h:\n\t\th += 1\ny = a[-1] - h\nprint(sum(a) - x - y)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.sort()\ns = sum(a)\nh = 0\nreq = 0\nm_h = a[-1]\nif a[0] != 0:\n\treq = 1\n\th = 1\nfor i in range(1, n):\n\tif a[i] > a[i - 1]:\n\t\th += 1\n\t\treq += 1\n\telif a[i] != 0:\n\t\tif h < a[i]:\n\t\t\treq += 1\n\t\t\th += 1\n\t\telse:\n\t\t\treq += 1\nreq += max(0, m_h - h)\nprint(s - req)\n", "(x, y) = [int(i) for i in input().split()]\na = sorted([int(i) for i in input().split()])\nt = z = 0\nfor i in range(x):\n\tz += a[i] - t\n\tif z <= i:\n\t\tz += 1\n\tt = a[i]\nprint(sum(a) - z)\n", "R = lambda : map(int, input().rstrip().split())\n(n, m) = R()\na = list(sorted(R()))\nx = 0\nprev = 0\nfor i in range(1, n + 1):\n\tx += 1\n\tif a[i - 1] > prev:\n\t\tprev += 1\nx += a[n - 1] - prev\nprint(sum(a) - x)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\nh = max(a)\na.sort()\na.reverse()\na.append(0)\nans = sum(a)\nfor i in range(n):\n\tif a[i + 1] >= a[i]:\n\t\ta[i + 1] = a[i] - 1\n\tans -= max(a[i] - a[i + 1], 1)\nprint(ans)\n", "(n, m) = [int(x) for x in input().split(' ')]\nz = [int(x) for x in input().split(' ')]\nz.sort()\n(a, b, ans) = (0, 0, 0)\nfor i in range(n - 1):\n\tif z[i] <= 1:\n\t\tif z[i] == 1:\n\t\t\ta = 1\n\t\tcontinue\n\tif z[i] > 1:\n\t\tif z[i] > a:\n\t\t\tans += z[i] - 1\n\t\telse:\n\t\t\tans += a - 1\n\ta += 1\n\ta = min(a, z[i])\nif z[-1] > a:\n\tans += a\nelse:\n\tans += z[-1] - 1\nprint(ans)\n", "line1 = input().split()\n(row, col) = (int(line1[0]), int(line1[1]))\nblocks = [int(x) for x in input().split()]\n\ndef count_removable(blocks):\n\trows = len(blocks)\n\tcols = max(blocks)\n\tblocks.sort()\n\tcan_replace = 1\n\tfor i in range(1, len(blocks)):\n\t\tblock = blocks[i]\n\t\tif block > can_replace:\n\t\t\tcan_replace += 1\n\tkeep = rows + cols - can_replace\n\treturn sum(blocks) - keep\nprint(count_removable(blocks))\n", "import collections\n(x, y) = map(int, input().split())\nblocks = [(k, v) for (k, v) in collections.Counter(map(int, input().split())).items()]\nblocks.sort(key=lambda x: x[0], reverse=True)\ntotal = 0\nnext_h = blocks[0][0]\nfor (h, c) in blocks:\n\tif next_h > h:\n\t\ttotal -= next_h - h\n\ttotal += h * c - c\n\tnext_h = max(0, min(h, next_h) - c)\ntotal -= next_h\nprint(total)\n", "(n, m) = [int(x) for x in input().split()]\na = [0] + [int(x) for x in input().split()]\na.sort()\nasum = sum(a)\namax = a[n]\nd = 0\nfor i in range(1, n + 1):\n\tif a[i] + d < i:\n\t\td = i - a[i]\nprint(asum - (n + (amax - n) + d))\n", "(n, m) = map(int, input().split())\na = [int(x) for x in input().split()]\na.sort()\nc = 0\nmaxi = 0\nfor i in range(n):\n\tif maxi + 1 > a[i]:\n\t\tc += a[i] - 1\n\t\tpass\n\telse:\n\t\tmaxi += 1\n\t\tc += a[i] - 1\nprint(c - a[-1] + maxi)\n", "import math\nimport sys\nDEBUG = False\n\ndef inp():\n\treturn sys.stdin.readline().rstrip()\n\ndef dprint(*value, sep=' ', end='\\n'):\n\tif DEBUG:\n\t\tprint(*value, sep=sep, end=end)\n\ndef solve(N, M, A):\n\tA.sort(reverse=True)\n\tlh = A[0]\n\tcnt = 1\n\tfor a in A[1:]:\n\t\tif lh == 1:\n\t\t\tcnt += 1\n\t\telif lh - 1 <= a:\n\t\t\tcnt += 1\n\t\t\tlh -= 1\n\t\telse:\n\t\t\tcnt += lh - a\n\t\t\tlh = a\n\tcnt += lh - 1\n\treturn sum(A) - cnt\n\ndef main():\n\t(N, M) = [int(e) for e in inp().split()]\n\tA = [int(e) for e in inp().split()]\n\tassert len(A) == N\n\tprint(solve(N, M, A))\nmain()\n", "a = input()\nn = int(a.split()[0])\nm = int(a.split()[1])\nb = input()\nl = list(map(int, b.split()))\nl.sort()\nh = 0\nk = 0\nfor i in range(n):\n\tif h < l[n - 1] and l[i] >= h + 1:\n\t\th = h + 1\n\t\tk = k + 1\n\telse:\n\t\tk = k + 1\nk = k + l[n - 1] - h\nprint(sum(l) - k)\n", "import sys\n(n, m, a) = (0, 0, 0)\n\ndef removeFromStack(arr):\n\tarr.sort()\n\t(cnt, last, sum) = (0, 0, 0)\n\tfor i in range(len(arr)):\n\t\tsum += arr[i]\n\t\tcnt += 1\n\t\tif arr[i] > last:\n\t\t\tlast += 1\n\tcnt += arr[len(arr) - 1] - last\n\treturn sum - cnt\n\ndef main():\n\twords = nextLineWords()\n\tn = int(words[0])\n\tm = int(words[1])\n\twords = nextLineWords()\n\ta = []\n\tfor word in words:\n\t\ta.append(int(word))\n\tprint(removeFromStack(a))\n\ndef nextLineWords():\n\treturn sys.stdin.readline().split()\nmain()\n", "(n, m) = map(int, input().split())\nl = list(map(int, input().split()))\nl.sort()\nres = 0\npre = l[0] - 1\nfor i in range(len(l) - 1):\n\tif l[i] < l[i + 1]:\n\t\tres += l[i]\n\t\tpre += l[i + 1] - l[i] - 1\n\telse:\n\t\tres += l[i] - 1\n\t\tif pre > 0:\n\t\t\tpre -= 1\n\t\t\tres += 1\nprint(res)\n", "import math\nn = [int(i) for i in input().split(' ')]\ndata = [int(i) for i in input().split(' ')]\ndata.sort()\ndata.reverse()\n(p, s) = (0, 0)\nfor i in range(0, n[0] - 1):\n\tif data[i] <= data[i + 1] and data[i] > 1:\n\t\ts += data[i + 1] + 1 - data[i]\n\t\tdata[i + 1] = data[i] - 1\n\tif data[i] == 1:\n\t\ts += data[i + 1] - 1\n\t\tdata[i + 1] = 1\nfor i in range(n[0] - 1):\n\tif data[i] > 1:\n\t\ts += data[i + 1]\nprint(s)\n", "import sys\nimport math\nline1 = sys.stdin.readline().strip()\nline2 = sys.stdin.readline().strip()\n(a, b) = line1.split()\n(w, h) = (int(a), int(b))\n(w, h)\nheights = line2.split()\nheights = list(map(lambda l: int(l), heights))\nh = min(max(heights), h)\nheights = list(filter(lambda h: h > 0, heights))\nw = min(len(heights), w)\nwtc = w\nhtc = h\nneeded = 0\nif w == 1:\n\tprint(0)\nelse:\n\theights.sort(reverse=True)\n\tfor i in range(len(heights)):\n\t\tif i == len(heights) - 1:\n\t\t\tcurr_h = heights[i]\n\t\t\tif htc <= 0:\n\t\t\t\tneeded += 1\n\t\t\telse:\n\t\t\t\tneeded += htc\n\t\telse:\n\t\t\tdh = htc - heights[i + 1]\n\t\t\tif dh > 0:\n\t\t\t\thtc -= dh\n\t\t\t\tneeded += dh\n\t\t\telif dh == 0:\n\t\t\t\thtc -= 1\n\t\t\t\tneeded += 1\n\t\t\telse:\n\t\t\t\thtc -= 1\n\t\t\t\tneeded += 1\n\tprint(sum(heights) - needed)\n", "(n, m) = map(int, input().strip().split())\narr = list(map(int, input().strip().split()))\n(sum1, sum2) = (sum(arr), 0)\narr = sorted(arr)\nmaxi = arr[n - 1]\nsum2 = 0\ncount = 0\nif n == 1:\n\tprint(0)\nelse:\n\tfor i in range(n):\n\t\tif i == n - 1:\n\t\t\tsum2 += arr[n - 1] - count\n\t\telif count + 1 == maxi:\n\t\t\tsum2 += 1\n\t\telif count + 1 <= arr[i]:\n\t\t\tsum2 += 1\n\t\t\tcount += 1\n\t\telse:\n\t\t\tsum2 += 1\n\tprint(sum1 - sum2)\n", "(n, m) = tuple(map(int, input().split()))\na = list(map(int, input().split()))\na.sort()\ntotal = sum(a)\nselected = 0\nfor i in range(0, n):\n\tif a[i] > selected:\n\t\tselected += 1\nleft = a[-1] - selected\nprint(total - left - n)\n", "import math\n(n, m) = map(int, input().split())\na = sorted(list(map(int, input().split())))\nres = 0\nnr = 1\nf = 1\nfor i in range(len(a) - 1):\n\tif a[i] != 0:\n\t\tif a[i] == 1:\n\t\t\tnr = 2\n\t\t\tcontinue\n\t\tif nr > a[i]:\n\t\t\tres += max(0, max(0, nr - 1) - 1)\n\t\telse:\n\t\t\tres += max(0, a[i] - nr) + max(0, nr - 1)\n\t\tif a[i] - nr >= 0:\n\t\t\tf = 0\n\t\tif f == 0:\n\t\t\tnr += 1\n\t\t\tf = 1\nif nr > a[-1]:\n\tres += max(0, max(0, nr - 1) - 1)\nelse:\n\tres += max(0, nr - 1)\nprint(res)\n", "(n, m) = map(int, input().split())\narr = list(map(int, input().split()))\narr.sort(reverse=True)\nright = arr[0]\nc = 0\nfor i in range(n):\n\tif arr[i] >= right:\n\t\tc += 1\n\t\tright -= 1\n\telse:\n\t\tc += 1\n\t\tright = arr[i] - 1\n\tif right == 0:\n\t\tbreak\nprint(sum(arr) - (n - c) - arr[0])\n", "(n, m) = map(int, input().split())\narr = [int(x) for x in input().split()]\ntot = sum(arr)\nma = max(arr)\narr.sort()\nfor i in range(n):\n\tif arr[i] == 0:\n\t\tdel arr[i]\nl = len(arr)\nif True:\n\th = 0\n\tleft = 0\n\tfor i in range(l - 1):\n\t\tif arr[i] > h:\n\t\t\th += 1\n\t\tleft += 1\n\tif h == ma:\n\t\tleft += 1\n\tleft += ma - h\nprint(tot - left)\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(n, k) = map(int, input().split())\narr = list(map(int, input().split()))\nm = max(arr)\narr.sort()\nvar = m - 1\nif var == 0:\n\tprint(sum(arr) - n)\nelse:\n\tans = 0\n\tfor i in range(n - 1):\n\t\tif arr[i] > ans:\n\t\t\tans += 1\n\tf = m - 1 - ans\n\tprint(sum(arr) - n if ans >= m - 1 else sum(arr) - n - f)\n", "(n, m) = map(int, input().strip().split())\narr = list(map(int, input().strip().split()))\narr = sorted(arr, reverse=True)\nak = []\nfor i in range(n):\n\tak.append(arr[i])\nfor i in range(n - 1):\n\tif arr[i] == min(arr[i], arr[i + 1]):\n\t\tarr[i + 1] = max(1, arr[i] - 1)\nans = 0\nfor i in range(n):\n\tans += ak[i] - arr[i]\nfor i in range(n - 1):\n\tif arr[i] != 1:\n\t\tans += arr[i + 1]\nif len(arr) > 1:\n\tif arr[n - 1] != 1:\n\t\tans += arr[n - 1] - arr[n - 1]\nelse:\n\tans = 0\nprint(ans)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\nans = sum(a)\na.sort()\nlastlevel = 0\nlevel = 0\ngot = 0\nfor i in a:\n\tgot = max(got, i)\n\tlevel = min(level + 1, got)\n\tif i > 0:\n\t\tans -= 1\n\t\tlastlevel = level\nans -= got - level\nprint(ans)\n", "input()\nsl = map(int, input().split())\nsl = sorted(sl)\nh = t = 0\nfor s in sl[:-1]:\n\tif s > h:\n\t\th += 1\n\tt += s - 1\nif h == sl[-1]:\n\tt += h - 1\nelse:\n\tt += h\nprint(t)\n", "(n, m) = map(int, input().split())\na = [int(s) for s in input().split()]\na = sorted(a)\ncurrent = a[n - 1]\nk = 0\nif n == 1:\n\tprint(0)\n\texit()\nfor i in range(n - 1, -1, -1):\n\tif i > 0 and a[i - 1] < current - 1:\n\t\ta[i] -= current - 1 - a[i - 1]\n\t\tk += a[i] - 1\n\t\tcurrent = a[i - 1]\n\telif a[i] >= current:\n\t\tk += a[i] - current\n\t\tif i != 0:\n\t\t\tk += max(current - 1, 0)\n\t\tcurrent -= 1\n\tcurrent = max(current, 1)\nprint(k)\n", "(n, m) = [int(x) for x in input().split()]\nL = [int(x) for x in input().split()]\nD = {}\nfor i in L:\n\tif i in D:\n\t\tD[i] += 1\n\telse:\n\t\tD[i] = 1\nS = sorted(D.keys(), reverse=True) + [0]\nheight = S[0]\nextra = 0\nfor i in range(0, len(S) - 1):\n\theight -= max(D[S[i]], max(0, min(S[i], height) - S[i + 1]))\nprint(sum(L) - S[0] + height)\n", "I = input\n(n, m) = map(int, I().split())\na = list(map(int, I().split()))\na.sort()\nl = 0\nh = a[n - 1]\nans = 0\nfor i in range(n):\n\tif l == h:\n\t\tans += a[i] - 1\n\telif a[i] < l + 1:\n\t\tif a[i] > 1:\n\t\t\tans += a[i] - 1\n\telif a[i] >= l + 1:\n\t\tif i != n - 1:\n\t\t\tif a[i] > 1:\n\t\t\t\tans += a[i] - 1\n\t\t\tl += 1\n\t\telif a[i] > 1:\n\t\t\tans += l\nprint(ans)\n", "from functools import reduce\nimport math\nfrom decimal import *\n\ndef factors(n):\n\treturn set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))\n\ndef sol():\n\t(w, h) = list(map(int, input().split()))\n\tarr = list(map(int, input().split()))\n\tif w == 1:\n\t\tprint(0)\n\t\treturn 0\n\tt = 0\n\ts = sum(arr)\n\tarr.sort()\n\tarr.reverse()\n\tind = 0\n\tout = []\n\twhile ind < w - 1:\n\t\tif arr[ind] <= arr[ind + 1]:\n\t\t\tout.append(1)\n\t\t\tarr[ind + 1] = max(arr[ind] - 1, 1)\n\t\tind += 1\n\tfor i in range(w - 1):\n\t\tt += max(arr[i] - arr[i + 1], 1)\n\tt += arr[-1]\n\tprint(s - t)\nsol()\n", "import sys\ninput = sys.stdin.readline\n(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.sort(reverse=True)\nans = 0\nneed = max(a)\nfor col in a:\n\tif col == 1 and need == 1:\n\t\tans += 1\n\telse:\n\t\tans += max(1, need - col + 1)\n\t\tneed = max(1, min(need - 1, col - 1))\nif need != 1:\n\tans += need\nprint(sum(a) - ans)\n", "(n, m) = map(int, input().split())\nl = list(map(int, input().split()))\ns = 0\nl.sort()\nk = 0\nfor i in range(n - 1, 0, -1):\n\tif l[i] > l[i - 1]:\n\t\ts += l[i - 1]\n\telif l[i] == l[i - 1] and l[i] > 1:\n\t\ts += l[i]\n\t\tl[i - 1] = l[i - 1] - 1\n\telse:\n\t\ts += l[i - 1] - l[i]\n\t\tif l[i] > 1:\n\t\t\ts += l[i]\n\t\t\tl[i - 1] = l[i] - 1\n\t\telse:\n\t\t\tl[i - 1] = l[i]\nprint(s)\n", "(n, m) = map(int, input().split())\nseq = sorted(map(int, input().split()))\nans = 0\nfor i in range(n):\n\tans += seq[i] - 1\nwait = 0\nlast = seq[-1]\nfor i in range(n - 1, 0, -1):\n\twait += 1\n\tif last - seq[i - 1] > wait:\n\t\tans -= last - seq[i - 1] - wait\n\t\twait = 0\n\t\tlast = seq[i - 1]\nif last - 1 > wait:\n\tans -= last - 1 - wait\n\twait = 0\nprint(ans)\n", "(n, m) = map(int, input().split())\nL = sorted(map(int, input().split()))\nma = 0\nc = 0\nfor i in range(n):\n\tif L[i] > ma:\n\t\tc += 1\n\t\tma += 1\nprint(sum(L) - n - max(L) + c)\n", "def main():\n\t(n, m) = map(int, input().split())\n\ta = list(reversed(sorted(map(int, input().split()))))\n\tres = 0\n\th = a[0]\n\tb = []\n\tfor x in a:\n\t\tif x > h:\n\t\t\tres += x - h\n\t\th = min(h, x)\n\t\tb.append(h)\n\t\tif h > 1:\n\t\t\th -= 1\n\tfor i in range(len(b) - 1):\n\t\tif b[i] > b[i + 1]:\n\t\t\tres += b[i + 1]\n\tprint(res)\nmain()\n", "input1 = [int(x) for x in input().split()]\nn = input1[0]\nm = input1[1]\n_arr = [int(x) for x in input().split()]\narr = sorted(_arr)\nresult = 0\nheight = 0\nfor i in range(n - 1):\n\tif arr[i] > height:\n\t\theight += 1\n\tresult += 1\nif arr[-1] == height:\n\tresult += 1\nelse:\n\tresult += arr[-1] - height\nprint(sum(arr) - result)\n", "(n, m) = map(int, input().split())\nlistik = sorted(list(map(int, input().split())))\nsumma = 0\nlast = 0\nfor i in range(n):\n\tif listik[i] > last:\n\t\tlast += 1\n\t\tsumma += 1\nprint(sum(listik) - n - listik[-1] + summa)\n", "[n, m] = [int(i) for i in input().split()]\na = sorted([int(i) for i in input().split()])\na = [i for i in a if i > 0]\nneedLeft = 1\nj = 1\nfor i in range(n):\n\tif i == n - 1:\n\t\tneedLeft += a[i] - j\n\telif a[i + 1] > j:\n\t\tj += 1\n\t\tneedLeft += 1\n\telse:\n\t\tneedLeft += 1\ncanDelete = sum(a) - needLeft\nprint(canDelete)\n", "import sys\n(n, m) = map(int, input().split())\nA = list(map(int, input().split()))\nif n == 1:\n\tprint(0)\n\tsys.exit()\nA.sort(reverse=True)\nNOW = A[0]\nANS = 1\ni = 1\nwhile i < n:\n\tif A[i] == A[i - 1]:\n\t\tNOW = max(1, NOW - 1)\n\t\tANS += 1\n\telif A[i] >= NOW - 1:\n\t\tANS += 1\n\t\tNOW = max(NOW - 1, 1)\n\telse:\n\t\tANS += max(1, NOW - A[i])\n\t\tNOW = A[i]\n\ti += 1\nANS += NOW - 1\nprint(sum(A) - ANS)\n", "nm = input().split(' ')\n(n, m) = list(map(lambda s: int(s), nm))\nstacksS = input().split(' ')\nstacks = list(map(lambda s: int(s), stacksS))\nsumStacks = sum(stacks)\nstacks = sorted(stacks)\ni = 0\nfor s in stacks:\n\tif s > i:\n\t\ti += 1\nrightView = stacks[n - 1] - i\nprint(sumStacks - rightView - n)\n", "import sys\nreadints = lambda : map(int, input().strip('\\n').split())\n(n, m) = readints()\na = list(readints())\na = list(reversed(sorted(a)))\nif n == 1:\n\tprint(0)\n\tsys.exit(0)\nans = sum(a)\nneed = a[0]\nfor x in a:\n\tif x > need:\n\t\tans -= 1\n\t\tneed -= 1\n\telif x == need:\n\t\tans -= 1\n\t\tneed -= 1\n\telif x < need:\n\t\tans -= 1\n\t\tans -= need - x\n\t\tneed = x - 1\nans -= max(0, need)\nprint(ans)\n", "(n, m) = map(int, input().split())\na = [int(o) for o in input().split()]\na = sorted(a)\nprev = 0\nd = 0\nfor i in range(n):\n\td += a[i] - prev\n\tif d <= i:\n\t\td += 1\n\tprev = a[i]\nprint(sum(a) - d)\n", "import os\nimport sys\nimport math\nimport collections\nimport cmath\n\ndef mp():\n\treturn map(int, input().split())\n\ndef inp():\n\treturn input()\n(n, m) = mp()\nar = list(mp())\nar.sort()\nj = 0\ncount = ar[0] - 1\nif m == 1 or n == 1:\n\tprint(0)\nelse:\n\tfor i in range(n):\n\t\tif ar[i] > j:\n\t\t\tj += 1\n\tprint(sum(ar) - n - max(ar) + j)\n", "ar1 = str(input()).split(' ')\nar2 = sorted(str(input()).split(' '))\nar3 = []\nfor el in ar2:\n\tar3.append(int(el))\nar4 = sorted(ar3)\nn = int(ar1[0])\nm = int(ar1[1])\nsumm1 = 0\nfor i in range(len(ar2)):\n\tsumm1 = summ1 + int(ar2[i])\nsumm = 0\nnum = 0\nj = 1\nfor i in range(len(ar4)):\n\tif j > int(ar4[i]):\n\t\tnum += 1\n\t\tj -= 1\n\tj += 1\nif num > 0:\n\tprint(summ1 - num - int(ar4[len(ar4) - 1]))\nelse:\n\tprint(summ1 - ar4[len(ar4) - 1])\n", "import sys\ninput = sys.stdin.buffer.readline\n(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.sort(reverse=True)\ncnt = a[0] + n - 1\nma = a[0] - 1\nfor i in range(1, n):\n\tif ma == 0:\n\t\tbreak\n\tif ma < a[i]:\n\t\tcnt -= 1\n\t\tma -= 1\n\telse:\n\t\tma = a[i] - 1\n\t\tcnt -= 1\nprint(sum(a) - cnt)\n", "(n, m) = map(int, input().split())\nl = list(map(int, input().split()))\nif n == 1 or m == 1:\n\tprint(0)\nelse:\n\tans = sum(l)\n\tl.sort(reverse=True)\n\tfor i in range(n - 1):\n\t\tif l[i] <= l[i + 1]:\n\t\t\tl[i + 1] = l[i] - 1\n\tl.append(0)\n\tfor i in range(n):\n\t\tans -= max(1, l[i] - l[i + 1])\n\tprint(ans)\n", "(n, m) = map(int, input().split(' '))\na = list(map(int, input().split(' ')))\na.sort()\nsm = sum(a)\nb = []\nfor elem in a:\n\tif elem != 0:\n\t\tb.append(elem)\nans = 0\nsh = 0\nfor i in range(len(b)):\n\tif b[i] > sh:\n\t\tsh += 1\nprint(sm - max(a) - len(b) + sh)\n", "(n, m) = map(int, input().split())\na = sorted([int(i) for i in input().split()])\nans = 0\nc = a[n - 1]\nif n == 1:\n\tprint(0)\n\traise SystemExit\nfor i in range(n - 1, -1, -1):\n\tif i > 0 and a[i - 1] < c - 1:\n\t\ta[i] -= c - 1 - a[i - 1]\n\t\tans += a[i] - 1\n\t\tc = a[i - 1]\n\telif a[i] >= c:\n\t\tans += a[i] - c\n\t\tif i:\n\t\t\tans += max(c - 1, 0)\n\t\tc -= 1\n\tc = max(c, 1)\nprint(ans)\n", "(n, m) = map(int, input().split())\na = [int(x) for x in input().split()]\na.sort()\nj = 1\nfor i in a:\n\tif i >= j:\n\t\tj += 1\nprint(max(sum(a) - n - max(max(a) - j + 1, 0), 0))\n", "import sys\nimport math\nfileoperation = 0\nif fileoperation:\n\torig_stdout = sys.stdout\n\torig_stdin = sys.stdin\n\tinputfile = open('W:/Competitive Programming/input.txt', 'r')\n\toutputfile = open('W:/Competitive Programming/output.txt', 'w')\n\tsys.stdin = inputfile\n\tsys.stdout = outputfile\nmod = 1000000007\n\ndef nospace(l):\n\tans = ''.join((str(i) for i in l))\n\treturn ans\nt = 1\nfor tt in range(t):\n\t(n, k) = map(int, sys.stdin.readline().split(' '))\n\ta = list(map(int, sys.stdin.readline().split(' ')))\n\ta.sort()\n\tans = 0\n\tc = 1\n\tfor i in range(n):\n\t\tif c > a[n - 1] or c > a[i]:\n\t\t\tans += a[i] - 1\n\t\t\tcontinue\n\t\tif i != n - 1:\n\t\t\tans += a[i] - 1\n\t\t\tc += 1\n\t\telse:\n\t\t\tans += c - 1\n\tprint(ans)\nif fileoperation:\n\tsys.stdout = orig_stdout\n\tsys.stdin = orig_stdin\n\tinputfile.close()\n\toutputfile.close()\n", "(n, m) = map(int, input().split())\nA = list(map(int, input().split()))\nk = max(A)\ns = sum(A)\nx = 0\na = 0\nA.sort()\nfor i in range(0, n):\n\tif A[i] > x:\n\t\tx += 1\n\t\ta += 1\n\telse:\n\t\ta += 1\nif k > x:\n\ta += k - x\nprint(s - a)\n", "import math\n\ndef solve(n, m, a):\n\tsz = len(a)\n\tlo = 0\n\tmin_nid = 0\n\tsu = 0\n\tlis = sorted(a)\n\tfor i in lis:\n\t\tmin_nid += 1\n\t\tsu += i\n\t\tif i > lo:\n\t\t\tlo += 1\n\tmin_nid += lis[-1] - lo\n\treturn su - min_nid\n\ndef wew(l1, l2):\n\t(n, m) = list(map(int, l1.split()))\n\ta = list(map(int, l2.split()))\n\treturn solve(n, m, a)\nfrom sys import stdin\n\ndef main():\n\tprint(wew(stdin.readline(), stdin.readline()))\nmain()\n", "def run():\n\t(n, mmm) = map(int, input().split())\n\tarr = list(map(int, input().split()))\n\tarr.sort()\n\tans = 0\n\tfor i in range(n):\n\t\tif arr[i] > ans:\n\t\t\tans += 1\n\tleft = arr[n - 1] - ans\n\tsol = sum(arr) - n - left\n\tprint(sol)\nrun()\n", "import math\n(n, m) = map(int, input().split())\na = [int(i) for i in input().split()]\nif n == 1:\n\tprint(0)\n\texit()\nelse:\n\ta.sort()\n\t_max = max(a)\n\tans = 0\n\tfor i in range(n - 1, -1, -1):\n\t\tif a[i] >= _max:\n\t\t\tans += a[i] - 1\n\t\t\t_max -= 1\n\t\telif a[i] < _max:\n\t\t\tans -= abs(a[i] - _max)\n\t\t\tans += a[i] - 1\n\t\t\t_max = a[i] - 1\n\tif _max > 0:\n\t\tans -= _max\n\tprint(ans)\n", "(n, m) = [int(x) for x in input().split()]\na = [int(x) for x in input().split()]\na.sort()\nlast = 0\ntotal = 0\nfor i in range(n - 1):\n\tif a[i] > 0:\n\t\ttotal += a[i] - 1\n\t\tlast = min(last + 1, a[i])\nprint(total + max(a[n - 1] - max(1, a[n - 1] - last), 0))\n", "(n, m) = list(map(int, input().split()))\na = list(map(int, input().split()))\nif n == 1:\n\tprint(0)\n\texit(0)\nk = 0\nfor i in a:\n\tif i > 0:\n\t\tk += 1\na.sort()\na = a[::-1]\nc = max(a)\nd = 0\nfor i in a:\n\tif c > i:\n\t\tc = i\n\tif c <= 1:\n\t\tbreak\n\td += 1\n\tc -= 1\nans = sum(a) - (max(a) + k - 1) + d\nif d == n and min(a) > 1:\n\tans -= 1\nprint(ans)\n", "_ = input()\na = sorted(map(int, input().split()))\ni = s = 0\nfor x in a:\n\ts += x - 1\n\ti = min(x, i + 1)\nprint(s - a[-1] + i)\n", "(n, m) = map(int, input().split())\na = sorted(map(int, input().split()))\nans = 0\ncur = 0\nfor b in a:\n\tif b > cur:\n\t\tans += 1\n\t\tcur += 1\n\telse:\n\t\tans += 1\nprint(sum(a) - (ans + max(a) - cur))\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.append(0)\na.sort()\nmx = a[n]\nans = 0\nfor i in range(n, 0, -1):\n\tcnt = max(1, mx - a[i - 1])\n\tans += a[i] - cnt\n\tmx -= cnt\nprint(ans)\n", "(n, t) = input().split()\nt = int(t)\nn = int(n)\nl = list(map(int, input().split()))\nm = max(l)\ns = sum(l)\nl.sort()\nj = 1\nc = 0\nfor i in l:\n\tif i >= j:\n\t\tj += 1\n\tc += 1\nc += m - j + 1\nprint(s - c)\n", "from collections import Counter, defaultdict\n(n, m) = list(map(int, input().split()))\nl = list(map(int, input().split()))\nl.sort()\nsumo = sum(l)\nc = 0\nans = 0\nfor i in l:\n\tans += 1\n\tif c < i:\n\t\tc += 1\nans += l[-1] - c\nprint(sumo - ans)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.sort()\nh = 0\nans = 0\nfor i in range(n - 1):\n\tans += a[i] - 1\n\tif a[i] > h:\n\t\th += 1\nif h < max(a):\n\tans += h\nelse:\n\tans += a[-1] - 1\nprint(ans)\n", "import math\nimport sys\n(n, k) = map(int, input().split())\na = list(map(int, input().split()))\na.sort()\ncnt = 0\ncut = 1\nf = 0\nfor i in a:\n\tif i == cut or i > cut:\n\t\tcnt += i - 1\n\t\tcut += 1\n\t\tf = 1\n\telif i < cut:\n\t\tcnt += i - 1\n\t\tcut = i + 1\n\t\tf = -1\nif f == 1:\n\tcut -= 1\nif a[-1] > cut:\n\tcnt -= a[-1] - cut\nprint(cnt)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.sort()\nmx = a[n - 1]\nremovE = 0\nc = 0\nfor i in range(n):\n\tif a[i] > c:\n\t\tc += 1\n\tremovE += a[i] - 1\nprint(removE - (mx - c))\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\ntotal = 0\nans = 0\nfor i in range(n):\n\ttotal += a[i]\na.sort()\nx = 0\ny = 0\nfor i in range(n):\n\tx += 1\n\tif a[i] > y:\n\t\ty += 1\nx += a[n - 1] - y\nans = total - x\nprint(ans)\n", "(n, m) = map(int, input().split())\nl = list(map(int, input().split()))\nif n == 1:\n\tprint(0)\nelse:\n\tl.sort()\n\tk = 0\n\tans = 0\n\tfor i in range(n):\n\t\tans += 1\n\t\tif l[i] > k:\n\t\t\tk += 1\n\tans += l[n - 1] - k\n\tprint(sum(l) - ans)\n", "(n, m) = list(map(int, input().split()))\na = list(map(int, input().split()))\na.sort(reverse=True)\nm = a[0]\nct = 0\nfor i in range(n):\n\tif m == 0:\n\t\tct += n - i\n\t\tbreak\n\tct += 1\n\tif a[i] < m:\n\t\tct += m - a[i]\n\t\tm = a[i]\n\tm -= 1\nprint(sum(a) - (m + ct))\n", "import sys\nimport math\nimport bisect\nfrom sys import stdin, stdout\nfrom math import gcd, floor, sqrt, log2, ceil\nfrom collections import defaultdict as dd\nfrom bisect import bisect_left as bl, bisect_right as br\nfrom bisect import insort\nfrom collections import Counter\nfrom collections import deque\nfrom heapq import heappush, heappop, heapify\nfrom itertools import permutations, combinations\nfrom itertools import accumulate as ac\nfrom random import randint as ri\nmod = int(1000000000.0) + 7\nip = lambda : int(stdin.readline())\ninp = lambda : map(int, stdin.readline().split())\nips = lambda : stdin.readline().rstrip()\nout = lambda x: stdout.write(str(x) + '\\n')\nt = 1\nfor _ in range(t):\n\t(n, m) = inp()\n\tarr = list(inp())\n\tarr.sort(reverse=True)\n\trequire = max(arr)\n\tans = 0\n\tfor i in range(n):\n\t\tif require == 0:\n\t\t\tans += 1\n\t\telif require == arr[i]:\n\t\t\trequire -= 1\n\t\t\tans += 1\n\t\telif require > arr[i]:\n\t\t\tans += require - arr[i]\n\t\t\trequire = arr[i]\n\t\t\trequire -= 1\n\t\t\tans += 1\n\t\telse:\n\t\t\trequire -= 1\n\t\t\tans += 1\n\tans += require\n\tans = sum(arr) - ans\n\tprint(ans)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\nsu = sum(a)\nma = max(a)\nif n == 1:\n\tprint(0)\nelse:\n\ta.sort()\n\tc = 0\n\tfor i in range(n - 1, 0, -1):\n\t\tif a[i] == 1:\n\t\t\tc += 1\n\t\telif a[i - 1] < a[i]:\n\t\t\tx = min(a[i], ma - c)\n\t\t\tif x <= a[i - 1]:\n\t\t\t\tc += 1\n\t\t\telse:\n\t\t\t\tc += x - a[i - 1]\n\t\telse:\n\t\t\tc += 1\n\tif ma - c > 0:\n\t\tc += ma - c\n\telse:\n\t\tc += 1\n\tprint(su - c)\n", "(n, m) = map(int, input().split())\nl = sorted(map(int, input().split()))\nlevel = 0\nfor v in l:\n\tlevel = min(v, level + 1)\nprint(sum(l) - n - l[-1] + level)\n", "(n, m) = input().split()\na = [int(i) for i in input().split()]\na.sort()\nif 1 in a:\n\tc = 1\nelse:\n\tc = 0\nans = cc = 0\nfor i in range(int(n)):\n\tif a[i] == c and cc == 0 or a[i] == c + 1:\n\t\tans += a[i] - 1\n\telif a[i] == c and cc > 0:\n\t\tans += c\n\t\tcc -= 1\n\telse:\n\t\tans += c\n\t\tcc += a[i] - c - 1\n\tc = a[i]\nif n == '1':\n\tprint(0)\nelse:\n\tprint(ans)\n", "(n, m) = map(int, input().split())\nl = list(map(int, input().split()))\nl.sort()\np = 0\nc = n\nfor i in range(n):\n\tif l[i] > p:\n\t\tp += 1\nc += l[len(l) - 1] - p\nprint(sum(l) - c)\n", "(n, m) = list(map(int, input().split()))\na = list(map(int, input().split()))\na.sort()\nmx = a[-1]\nt = 0\nans = 0\nfor i in a:\n\tif i > 0:\n\t\tif i > t:\n\t\t\tt += 1\n\t\tans += i - 1\nans -= mx - t\nprint(ans)\n", "(n, m) = map(int, input().split())\ntotal = red = prev = 0\na = []\nfor i in map(int, input().split()):\n\ttotal += i\n\ta.append(i)\na.sort()\nfor i in a:\n\tred += 1\n\tif i > prev:\n\t\tprev += 1\nred += a[-1] - prev\nans = total - red\nprint(ans)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\nif n == 1:\n\tprint(0)\n\texit()\nans = 0\na.sort(reverse=True)\np = a[0]\nfor j in range(n - 1):\n\tif p <= 0:\n\t\tans += a[j] - 1\n\t\tcontinue\n\tif a[j + 1] >= p - 1:\n\t\tans += a[j] - 1\n\t\tp -= 1\n\telse:\n\t\tk = p - a[j + 1]\n\t\tans += a[j] - k\n\t\tp -= k\nif p < 0:\n\tp = 0\nans += a[-1] - max(p, 1)\nprint(ans)\n", "s = input().split()\nn = int(s[0])\nm = int(s[1])\nstack = list(map(int, input().split()))\nstack.sort()\nh = 0\nans = 0\nfor i in stack:\n\tans += 1\n\tif i > h:\n\t\th += 1\nans += stack[-1] - h\nprint(sum(stack) - ans)\n", "inp = input().split()\nn = int(inp[0])\nm = int(inp[1])\ninp = input().split()\na = []\nfor i in inp:\n\ta.append(int(i))\nres = 0\na.sort(reverse=True)\ntr = a[0]\nfor i in range(0, len(a) - 1):\n\tif tr - 1 > a[i + 1]:\n\t\tres += tr - a[i + 1]\n\t\ttr = a[i + 1]\n\telse:\n\t\tres += 1\n\t\ttr = max(1, tr - 1)\nres += tr\nprint(sum(a) - res)\n", "(n, m) = [int(x) for x in input().split()]\na = [int(x) for x in input().split()]\ns = sum(a)\ntemp = sorted(a)\nres = temp[0]\nfor x in range(n - 1):\n\tif temp[x + 1] != temp[x]:\n\t\tres = res + (temp[x + 1] - temp[x])\n\tif x + 2 > res:\n\t\tres = res + 1\nprint(s - res)\n", "(n, m) = map(int, input().split())\nA = sorted(map(int, input().split()))\ncnt = 0\nprev = 0\nfor a in A:\n\tcnt += 1\n\tif a > prev:\n\t\tprev += 1\ncnt += A[-1] - prev\nprint(sum(A) - cnt)\n", "(n, m) = list(map(int, input().strip().split(' ')))\na = list(map(int, input().strip().split(' ')))\na.sort()\nx = 0\ny = 0\ncount = 0\nfor i in range(0, n):\n\tcount += a[i]\n\tif a[i] > y:\n\t\ty += 1\n\tx += 1\n\tif i == n - 1 and a[i] > y:\n\t\tx += a[i] - y\nprint(count - x)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.sort(reverse=True)\na.append(0)\n(j, s) = (a[0], 0)\nfor i in range(n):\n\tif j > 0:\n\t\tif j - 1 <= a[i + 1] and j - 1 > 0:\n\t\t\tj -= 1\n\t\t\ts += 1\n\t\telif j - 1 > a[i + 1]:\n\t\t\ts += j - a[i + 1]\n\t\t\tj = a[i + 1]\n\t\telif a[i + 1] > 0:\n\t\t\tj = 1\n\t\t\ts += 1\n\t\telif a[i + 1] == 0:\n\t\t\tj = 0\n\t\t\ts += 1\n\t\t\tbreak\n\telse:\n\t\tbreak\nprint(sum(a) - s)\n", "R = lambda : list(map(int, input().split()))\n(n, m) = R()\na = R()\na.sort()\ni = n - 1\nre = 0\nnow = a[i]\nwhile i > 0:\n\tif now > a[i - 1]:\n\t\tnow = a[i - 1]\n\t\tre += now\n\telif now == a[i - 1] and now > 1:\n\t\tnow -= 1\n\t\tre += now + 1\n\telse:\n\t\tif now > 1:\n\t\t\tnow -= 1\n\t\t\tre += now\n\t\tre += a[i - 1] - now\n\ti -= 1\nprint(re)\n", "from sys import stdin, stdout\nfrom math import gcd, sqrt\nfrom collections import deque\ninput = stdin.readline\nR = lambda : map(int, input().split())\nI = lambda : int(input())\nS = lambda : input().rstrip('\\n')\nL = lambda : list(R())\nP = lambda x: stdout.write(x)\nhg = lambda x, y: (y + x - 1) // x * x\npw = lambda x: 1 if x == 1 else 1 + pw(x // 2)\nchk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False\nN = 10 ** 6\n(r, c) = R()\na = sorted(L(), reverse=True) + [0]\ntp = a[0]\nans = 0\nfor i in range(1, r + 1):\n\tbt = max(0, min(tp - 1, a[i]))\n\tans += min(a[i - 1] - 1, a[i - 1] - (tp - bt))\n\ttp = bt\nprint(ans)\n", "(n, k) = map(int, input().split())\narr = list(sorted(map(int, input().split())))\nmx = 0\nsm = sum(arr)\nfor v in arr:\n\tif v > mx:\n\t\tmx += 1\nreserved = n + arr[-1] - mx\nprint(sm - reserved)\n", "def solve():\n\t(N, M) = map(int, input().split())\n\tA = [int(k) for k in input().split()]\n\tA.sort()\n\theight = 0\n\tfor i in range(1, N + 1):\n\t\tif A[i - 1] > height:\n\t\t\theight += 1\n\tres = N + (A[-1] - height)\n\tprint(sum(A) - res)\nsolve()\n", "import math\nfrom collections import deque\nimport sys\nsys.setrecursionlimit(10 ** 4)\n\ndef Divisors(n):\n\tl = []\n\ti = 2\n\twhile i <= math.sqrt(n):\n\t\tif n % i == 0:\n\t\t\tif n // i == i:\n\t\t\t\tl.append(i)\n\t\t\telse:\n\t\t\t\tl.append(i)\n\t\t\t\tl.append(n // i)\n\t\ti = i + 1\n\treturn l\n\ndef SieveOfEratosthenes(n):\n\tl = []\n\tprime = [True for i in range(n + 1)]\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\tfor p in range(2, n + 1):\n\t\tif prime[p]:\n\t\t\tl.append(p)\n\treturn l\n\ndef primeFactors(n):\n\tl = []\n\twhile n % 2 == 0:\n\t\tl.append(2)\n\t\tn = n / 2\n\tfor i in range(3, int(math.sqrt(n)) + 1, 2):\n\t\twhile n % i == 0:\n\t\t\tl.append(i)\n\t\t\tn = n / i\n\tif n > 2:\n\t\tl.append(n)\n\treturn l\n\ndef Factors(n):\n\tresult = []\n\tfor i in range(2, int(math.sqrt(n)) + 1):\n\t\tif n % i == 0:\n\t\t\tif i == n / i:\n\t\t\t\tresult.append(i)\n\t\t\telse:\n\t\t\t\tresult.append(i)\n\t\t\t\tresult.append(n // i)\n\tresult.append(1)\n\tresult.append(n)\n\treturn result\n\ndef maxSubArraySum(a):\n\tmax_so_far = 0\n\tmax_ending_here = 0\n\tsize = len(a)\n\tfor i in range(0, size):\n\t\tmax_ending_here = max_ending_here + a[i]\n\t\tif max_so_far < abs(max_ending_here):\n\t\t\tmax_so_far = max_ending_here\n\treturn max_so_far\n\ndef longestsubarray(arr, n, k):\n\tcurrent_count = 0\n\tmax_count = 0\n\tfor i in range(0, n, 1):\n\t\tif arr[i] % k != 0:\n\t\t\tcurrent_count += 1\n\t\telse:\n\t\t\tcurrent_count = 0\n\t\tmax_count = max(current_count, max_count)\n\treturn max_count\n\ndef main():\n\t(n, m) = list(map(int, input().split()))\n\tl = list(map(int, input().split()))\n\tl.sort()\n\tm = 1\n\tc = 0\n\tfor j in range(0, n - 1):\n\t\tif l[j] >= m:\n\t\t\tc += 1\n\t\t\tm += 1\n\t\telse:\n\t\t\tc += 1\n\tif l[n - 1] < m:\n\t\tc += 1\n\telse:\n\t\tc += l[n - 1] - m + 1\n\tprint(sum(l) - c)\nt = 1\nfor i in range(0, t):\n\tmain()\n", "(n, m) = map(int, input().split())\na = list(sorted(map(int, input().split())))\ns = 0\nh = 1\nfor i in range(len(a) - 1):\n\tif a[i] >= h:\n\t\th += 1\n\ts += a[i] - 1\ns += h - 1 if h <= a[len(a) - 1] else a[len(a) - 1] - 1\nprint(s)\n", "(n, m) = input().split()\na = sorted(map(int, input().split()))\ntot = 0\nlast_fill = 0\nreqd = 0\nfor x in a:\n\ttot += x\n\tif x > last_fill:\n\t\tlast_fill += 1\n\t\treqd += 1\n\telse:\n\t\treqd += 1\nreqd += a[-1] - last_fill\nprint(tot - reqd)\n", "(n, m) = list(map(int, input().split()))\nA = list(map(int, input().split()))\nnum_1 = 0\nj = 1\nA.sort()\nfor i in range(n - 1):\n\tnum_1 += 1\n\tif j + 1 <= A[i + 1]:\n\t\tj += 1\nnum_1 += A[-1] - j + 1\nprint(sum(A) - num_1)\n", "import sys\n\ndef solve(io):\n\tN = io.read_int()\n\tM = io.read_int()\n\tA = io.read_int_array(N)\n\tA = list(sorted(A))\n\tH = max(A)\n\tS = sum(A)\n\twant = 1\n\trem = 0\n\tfor v in A:\n\t\tif want <= v:\n\t\t\twant += 1\n\tkeep = H + N - (want - 1)\n\trem = S - keep\n\tio.println(rem)\n\nclass IO:\n\tin_stream = None\n\tout_stream = None\n\traw = ''\n\tbuf = []\n\tpos = 0\n\n\tdef __init__(self, input_stream, output_stream):\n\t\tself.in_stream = input_stream\n\t\tself.out_stream = output_stream\n\n\tdef read_to_buffer(self):\n\t\tself.raw = self.in_stream.readline().rstrip('\\n')\n\t\tself.buf = self.raw.split()\n\t\tself.pos = 0\n\n\tdef read_string(self):\n\t\twhile self.pos == len(self.buf):\n\t\t\tself.read_to_buffer()\n\t\tans = self.buf[self.pos]\n\t\tself.pos += 1\n\t\treturn ans\n\n\tdef read_int(self):\n\t\treturn int(self.read_string())\n\n\tdef read_float(self):\n\t\treturn float(self.read_string())\n\n\tdef read_string_array(self, N, offset=0):\n\t\tarr = [None] * offset\n\t\tfor _ in range(0, N):\n\t\t\tarr.append(self.read_string())\n\t\treturn arr\n\n\tdef read_int_array(self, N, offset=0):\n\t\tarr = [None] * offset\n\t\tfor _ in range(0, N):\n\t\t\tarr.append(self.read_int())\n\t\treturn arr\n\n\tdef read_float_array(self, N, offset=0):\n\t\tarr = [None] * offset\n\t\tfor _ in range(0, N):\n\t\t\tarr.append(self.read_float())\n\t\treturn arr\n\n\tdef read_line(self):\n\t\twhile self.pos == len(self.buf):\n\t\t\tself.read_to_buffer()\n\t\tif self.pos > 0:\n\t\t\traise ValueError('Cannot call read_line in the middle of a line.')\n\t\treturn self.raw\n\n\tdef print(self, s):\n\t\tself.out_stream.write(str(s))\n\n\tdef println(self, s):\n\t\tself.print(s)\n\t\tself.print('\\n')\n\n\tdef println_array(self, arr, sep=' '):\n\t\tself.println(sep.join((str(x) for x in arr)))\n\n\tdef flush_output(self):\n\t\tself.out_stream.flush()\npythonIO = IO(sys.stdin, sys.stdout)\nsolve(pythonIO)\npythonIO.flush_output()\n", "(n, m) = map(int, input().split())\na = [int(i) for i in input().split()]\nsum = 0\nfor i in range(n):\n\tsum += a[i]\na.sort()\na.reverse()\nnow = a[0]\ncnt = 1\nfor i in range(1, n):\n\twhile now > a[i] + 1:\n\t\tcnt = cnt + 1\n\t\tnow = now - 1\n\t\tif now == 1:\n\t\t\tbreak\n\tif now == 1:\n\t\tcnt = cnt + n - i\n\t\tbreak\n\tnow = now - 1\n\tcnt = cnt + 1\nwhile now > 1:\n\tnow = now - 1\n\tcnt = cnt + 1\nprint(sum - cnt)\n", "from math import inf as inf\nfrom math import *\nfrom collections import *\nimport sys\ninput = sys.stdin.readline\nt = 1\nwhile t:\n\tt -= 1\n\t(n, h) = map(int, input().split())\n\ta = list(map(int, input().split()))\n\ta.sort()\n\tre = 1\n\ts = 0\n\tfor i in range(n):\n\t\tif i == n - 1:\n\t\t\tif re > a[i]:\n\t\t\t\ts += a[i] - 1\n\t\t\telse:\n\t\t\t\ts += a[i] - (a[i] - re + 1)\n\t\t\tbreak\n\t\tif re <= a[i]:\n\t\t\tre += 1\n\t\ts += a[i] - 1\n\tprint(s)\n", "(n, m) = list(map(int, input().split()))\na = list(map(int, input().split()))\nif n == 1:\n\tprint(0)\nelse:\n\tcount = 0\n\ta.sort()\n\ttotal = sum(a)\n\tma = a[n - 1]\n\ty = 0\n\tcount = 0\n\tfor i in range(n):\n\t\tcount += 1\n\t\tif a[i] > y:\n\t\t\ty += 1\n\tprint(total - (ma - y) - count)\n", "(n, m) = map(int, input().split())\narr = list(map(int, input().split()))\narr.sort()\n(summ, minn) = (0, 0)\nfor i in range(n):\n\tsumm += arr[i] - 1\n\tminn = min(minn + 1, arr[i])\nprint(summ - arr[-1] + minn)\n", "[n, m] = [int(x) for x in input().split(' ')]\nA = [int(x) for x in input().split(' ')]\nA.sort()\nmaxRemove = 0\nmaxHeight = 0\nfor i in range(n):\n\tif i == n - 1:\n\t\tif A[i] > maxHeight:\n\t\t\tmaxRemove += maxHeight\n\t\telse:\n\t\t\tmaxRemove += A[i] - 1\n\telif i == 0:\n\t\tmaxHeight = 1\n\t\tmaxRemove += A[i] - 1\n\telse:\n\t\tmaxRemove += A[i] - 1\n\t\tif A[i] > maxHeight:\n\t\t\tmaxHeight += 1\nprint(maxRemove)\n", "from collections import Counter as C\n(n, m) = map(int, input().split())\nl = [*map(int, input().split())]\nc = sorted(C(l).items())\nres = 0\nj = 0\nfor (hi, ni) in c:\n\th = min(hi - j, ni) + j\n\tres += (hi - 1) * ni\n\tif h > j:\n\t\tj = h\nm = max(l)\nif j < m:\n\tres -= m - j\nprint(res)\n", "(n, m) = [int(i) for i in input().split()]\nA = [int(i) for i in input().split()]\nA.sort()\nsofar = 0\nfor i in range(n):\n\tif A[i] > sofar:\n\t\tsofar += 1\nprint(sum(A) - n - (A[-1] - sofar))\n", "from math import ceil, sqrt, log, gcd\n\ndef ii():\n\treturn int(input())\n\ndef si():\n\treturn input()\n\ndef mi():\n\treturn map(int, input().split())\n\ndef li():\n\treturn list(mi())\n\ndef main():\n\t(n, m) = mi()\n\ta = li()\n\ta.sort()\n\tans = 0\n\ts = 0\n\tfor i in range(n - 1):\n\t\tif a[i] > s:\n\t\t\tans += a[i] - 1\n\t\t\ts += 1\n\t\telse:\n\t\t\tans += a[i] - 1\n\tif a[n - 1] > s:\n\t\tx = a[n - 1] - s\n\t\tans += a[n - 1] - x\n\telse:\n\t\tans += a[n - 1] - 1\n\tprint(ans)\nmain()\n", "(n, m) = map(int, input().split())\nl = list(map(int, input().split()))\nl.sort()\nc = max(l)\nlow = 0\nans = 0\nfor i in range(n - 1):\n\tif l[i] > low:\n\t\tans += l[i] - 1\n\t\tlow += 1\n\telse:\n\t\tans += l[i] - 1\nif low == c:\n\tans += low - 1\nelse:\n\tans += low\nprint(ans)\n", "sum = 0\n(n, m) = map(int, input().split())\nara = list(map(int, input().split()))\nara.sort()\nfor i in range(n):\n\tsum += ara[i]\ncnt = 0\np = 0\nfor i in range(n):\n\tcnt += 1\n\tif ara[i] > p:\n\t\tp += 1\ncnt += ara[n - 1] - p\nprint(sum - cnt)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.sort()\nc = 0\nd = 0\ns = sum(a)\nfor i in range(n):\n\tc += 1\n\tif a[i] > d:\n\t\td += 1\nc += a[n - 1] - d\nprint(s - c)\n", "(n, m) = list(map(int, input().rstrip().split()))\ndata = list(map(int, input().rstrip().split()))\n\ndef mergesort(l):\n\tif len(l) == 1:\n\t\treturn l\n\tllower = []\n\tlupper = []\n\tfor i in range(0, int(len(l) / 2)):\n\t\tllower.append(l[i])\n\tfor i in range(int(len(l) / 2), len(l)):\n\t\tlupper.append(l[i])\n\tslower = mergesort(llower)\n\tsupper = mergesort(lupper)\n\tb = 0\n\tu = 0\n\tsort = []\n\twhile b < len(slower) and u < len(supper):\n\t\tif slower[b] <= supper[u]:\n\t\t\tsort.append(slower[b])\n\t\t\tb = b + 1\n\t\telif supper[u] < slower[b]:\n\t\t\tsort.append(supper[u])\n\t\t\tu = u + 1\n\tif b == len(slower):\n\t\tfor i in range(u, len(supper)):\n\t\t\tsort.append(supper[i])\n\telif u == len(supper):\n\t\tfor i in range(b, len(slower)):\n\t\t\tsort.append(slower[i])\n\treturn sort\nsort = mergesort(data)\nheight = sort[n - 1]\ntotal = 0\nfor i in range(0, n - 1):\n\tif sort[n - i - 1] == sort[n - i - 2]:\n\t\theight += -1\n\t\ttotal = total + 1\n\telif height > sort[n - i - 2]:\n\t\ttotal = total + height - sort[n - i - 2]\n\t\theight = sort[n - i - 2]\n\telse:\n\t\theight = height - 1\n\t\ttotal = total + 1\ntotal = total + max(1, height)\nprint(sum(data) - total)\n", "(n, m) = list(map(int, input().split()))\na = list(map(int, input().split()))\na.sort()\n(l, p, k) = (a[n - 1], 0, 0)\nfor i in range(n - 1):\n\tif p < l:\n\t\tif a[i] > p:\n\t\t\tk += a[i] - 1\n\t\t\tp += 1\n\t\telse:\n\t\t\tk += a[i] - 1\n\telse:\n\t\tk += a[i] - 1\nif p >= l:\n\tprint(k + (a[n - 1] - 1))\nelse:\n\tprint(k + (a[n - 1] - (l - p)))\n", "class IO:\n\n\tdef get(reader=str):\n\t\treturn reader(input().strip())\n\n\tdef gets(reader=str, delim=None):\n\t\treturn [reader(x) for x in input().strip().split(delim)]\n\n\tdef tostr(raw, writer=str, delim=' '):\n\t\treturn delim.join((writer(x) for x in raw))\n(n, m) = IO.gets(int)\na = IO.gets(int)\na.sort()\npos = 0\nfor roof in a:\n\tpos = min(pos + 1, roof)\nneed = len(a) + a[-1] - pos\nans = sum(a) - need\nprint(ans)\n", "(n, m) = map(int, input().split())\nl = list(map(int, input().split()))\nl.sort()\nt = 1\nans = 0\nfor i in range(n - 1):\n\tif l[i] >= t and t < l[n - 1]:\n\t\tt += 1\n\tans += l[i] - 1\nans += l[n - 1] - (l[n - 1] - t + 1)\nprint(ans)\n", "(n, m) = map(int, input().split())\nA = list(map(int, input().split()))\ns = sum(A)\nif n == 1:\n\tprint(0)\nelse:\n\tans = 0\n\tA.sort(reverse=True)\n\tfor i in range(n - 1):\n\t\tA[i] = min(A[i], m)\n\t\tif A[i] > A[i + 1]:\n\t\t\tans += A[i] - A[i + 1]\n\t\t\tm = min(m, A[i + 1])\n\t\telse:\n\t\t\tans += 1\n\t\t\tm = max(1, min(m, A[i] - 1))\n\tans += m\n\tprint(s - ans)\n", "def main():\n\t(n, m) = map(int, input().split())\n\ta = sorted(list(map(int, input().split())))\n\ts = 0\n\tfor i in range(len(a)):\n\t\ts += a[i]\n\tfor i in range(n - 2, -1, -1):\n\t\tif a[i + 1] > a[i]:\n\t\t\ts -= a[i + 1] - a[i]\n\t\telse:\n\t\t\ts -= 1\n\t\t\ta[i] = max(a[i + 1] - 1, 1)\n\tprint(s - a[0])\nmain()\n", "(n, h) = map(int, input().split())\nlst = list(map(int, input().split()))\nlst.sort(reverse=True)\nans = 0\nfor i in range(1, n):\n\tif lst[i - 1] == 1:\n\t\tans += lst[i] - 1\n\t\tlst[i] = 1\n\telif lst[i - 1] <= lst[i]:\n\t\tans += lst[i] - lst[i - 1] + 1\n\t\tlst[i] = lst[i - 1] - 1\nfor i in range(n - 1):\n\tif lst[i] != lst[i + 1]:\n\t\tans += lst[i + 1]\nprint(ans)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na = sorted(a)\nX = 0\nprev = 0\nfor i in range(1, n + 1):\n\tX += 1\n\tif a[i - 1] > prev:\n\t\tprev += 1\nX += a[n - 1] - prev\nprint(sum(a) - X)\n", "(n, m) = map(int, input().split())\nmas = list(map(int, input().split()))\nmas.sort()\n(res, a) = (0, mas[n - 1])\nfor i in range(n - 2, -1, -1):\n\t(q, w) = (mas[i + 1], mas[i])\n\tif q == w:\n\t\tres += q - 1\n\t\ta -= 1\n\telif a - 1 <= w:\n\t\tres += q - 1\n\t\ta -= 1\n\telse:\n\t\tres += q - (a - w)\n\t\ta = w\nres += min(mas[0] - 1, mas[0] - a)\nprint(res)\n", "(n, m) = list(map(int, input().split()))\nin_list = list(map(int, input().split()))\nin_list.sort()\nprev = 0\nmin_block = 0\nfor i in range(n):\n\tmin_block = min_block + in_list[i] - prev\n\tif min_block <= i:\n\t\tmin_block = min_block + 1\n\tprev = in_list[i]\nprint(sum(in_list) - min_block)\n", "(a, b) = map(int, input().split())\nl = list(map(int, input().split()))\nif a == 1:\n\tprint(0)\nelse:\n\tll = []\n\tl.sort()\n\t(s, p) = (0, 0)\n\tfor i in range(len(l)):\n\t\ts += 1\n\t\tif l[i] > p:\n\t\t\tp += 1\n\ts += max(l) - p\n\tprint(sum(l) - s)\n", "import re, math, decimal, bisect\n\ndef read():\n\treturn input().strip()\n\ndef iread():\n\treturn int(input().strip())\n\ndef viread():\n\treturn [int(_) for _ in input().strip().split()]\n(w, h) = viread()\n(ph, h) = (-1, -1)\n(keep, ttl) = (0, 0)\nfor s in sorted(viread() + [0], reverse=True):\n\tttl += s\n\tif h == -1:\n\t\th = s\n\telif h == 0:\n\t\tkeep += 1\n\telif s == ph:\n\t\th -= 1\n\t\tkeep += 1\n\telse:\n\t\tkeep += h - min(h - 1, s)\n\t\th = min(h - 1, s)\n\tph = s\nprint(ttl - keep)\n", "def exponat(lst):\n\t(result, count) = (0, 1)\n\tfor i in range(len(lst)):\n\t\tif count > lst[len(lst) - 1] or count > lst[i]:\n\t\t\tresult += lst[i] - 1\n\t\t\tcontinue\n\t\tif i != len(lst) - 1:\n\t\t\tresult += lst[i] - 1\n\t\t\tcount += 1\n\t\telse:\n\t\t\tresult += count - 1\n\treturn result\n(n, m) = [int(i) for i in input().split()]\na = [int(j) for j in input().split()]\nprint(exponat(sorted(a)))\n", "(n, m) = input().split()\na = [int(i) for i in input().split()]\na.sort()\nc = 0\nans = cc = 0\nfor i in range(int(n)):\n\tif cc > 1:\n\t\tans += cc - 1\n\t\tcc += -1 + a[i] - c\n\t\tans += a[i] - cc\n\telse:\n\t\tcc = max(1, a[i] - c)\n\t\tans += a[i] - cc\n\tc = a[i]\nprint(ans)\n", "(n, m) = map(int, input().split())\na = [int(x) for x in input().split()]\nc = sum(a)\nif n == 1:\n\tprint(0)\n\texit(0)\na.sort()\nres = 0\npocl = a[n - 1]\nf = False\nfor i in range(n - 2, -1, -1):\n\tif pocl > 1:\n\t\tif a[i] >= pocl:\n\t\t\tres += 1\n\t\t\tpocl -= 1\n\t\t\tres += a[i] - 1\n\t\telse:\n\t\t\tf = True\n\t\t\tpocl = a[i]\n\t\t\tres += 1\n\t\t\tres += a[i] - 1\n\t\t\tpocl -= 1\n\telif pocl == 1:\n\t\tif f:\n\t\t\tres += 1\n\t\tres += a[i] - 1\n\t\tpocl -= 1\n\telse:\n\t\tres += a[i] - 1\nprint(res)\n", "(n, m) = map(int, input().split())\narr = list(map(int, input().split()))\narr.sort()\n(lol, sum_) = (0, 0)\nfor i in range(n):\n\tif i < n - 1:\n\t\tsum_ += 1\n\t\tlol = min(lol + 1, arr[i])\n\telse:\n\t\tsum_ += max(arr[i] - lol, 1)\nprint(sum(arr) - sum_)\n", "from sys import stdin\n\ndef myfunction(arr, n):\n\tmy_sum = 0\n\tmy_min = 0\n\tif n == 1:\n\t\treturn 0\n\tfor i in range(n - 1):\n\t\tif arr[i] > my_min:\n\t\t\tmy_min += 1\n\t\tmy_sum += arr[i] - 1\n\tif arr[-1] == my_min:\n\t\tmy_sum += arr[i] - 1\n\telse:\n\t\tmy_sum += my_min\n\treturn my_sum\n(n, m) = list(map(int, stdin.readline().split()))\narr = list(map(int, stdin.readline().split()))\narr.sort()\nprint(myfunction(arr, n))\n", "(n, m) = map(int, input().split())\nA = list(map(int, input().split()))\nsum = 0\nA.sort()\nfor i in A:\n\tsum += i\nchoosen = 0\nfor i in range(n):\n\tif A[i] > choosen:\n\t\tchoosen += 1\nnot_choosen = A[-1] - choosen\nprint(sum - not_choosen - n)\n", "(n, k) = map(int, input().split())\na = list(map(int, input().split()))\na.sort(reverse=True)\nworst = 0\nmaxi = a[0]\na.append(0)\nfor i in range(n + 1):\n\tbad = maxi - a[i] - i\n\tworst = max(worst, bad)\nprint(sum(a) - n - worst)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.sort()\nm = max(a)\nc = 0\nlv = 0\nfor i in a:\n\tc += 1\n\tif i > lv:\n\t\tlv += 1\nc += m - lv\nprint(sum(a) - c)\n", "import collections, atexit, math, sys, bisect\nsys.setrecursionlimit(1000000)\n\ndef getIntList():\n\treturn list(map(int, input().split()))\ntry:\n\timport numpy\n\n\tdef dprint(*args, **kwargs):\n\t\tprint(*args, file=sys.stderr)\n\tdprint('debug mode')\nexcept Exception:\n\n\tdef dprint(*args, **kwargs):\n\t\tpass\ninId = 0\noutId = 0\nif inId > 0:\n\tdprint('use input', inId)\n\tsys.stdin = open('input' + str(inId) + '.txt', 'r')\nif outId > 0:\n\tdprint('use output', outId)\n\tsys.stdout = open('stdout' + str(outId) + '.txt', 'w')\n\tatexit.register(lambda : sys.stdout.close())\n(N, M) = getIntList()\nza = getIntList()\nza.sort(reverse=True)\nre = 0\nfor i in range(N - 1):\n\ta = za[i]\n\tb = za[i + 1]\n\tg = b\n\tif g >= a:\n\t\tt = a - 1\n\t\tif t < 1:\n\t\t\tt = 1\n\t\tre += g - t\n\t\tza[i + 1] = t\n\t\tre += a - 1\n\telse:\n\t\tre += g\nprint(re)\n", "(n, m) = map(int, input().split())\na = sorted(list(map(int, input().split())))\np = sum(a)\ni = n - 1\nwhile i > 0:\n\ta[i - 1] = min(a[i] - 1, a[i - 1])\n\tp -= a[i] - a[i - 1]\n\ti -= 1\nprint(p - max(a[0], 1))\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.append(0)\na.sort(reverse=True)\nall_s = sum(a)\ns = 0\nfor i in range(1, len(a)):\n\tif a[i - 1] > a[i]:\n\t\ts += a[i - 1] - a[i]\n\telif a[i - 1] == a[i]:\n\t\ts += 1\n\t\ta[i] -= 1\n\telse:\n\t\ts += 1\n\t\ta[i] = a[i - 1] - 1\nprint(all_s - s)\n", "nos = list(map(int, input().split()))\nn = nos[0]\ndata = list(map(int, input().split()))\nsuma = 0\nfor a in range(0, n):\n\tsuma += data[a]\ndata.sort()\ndata.reverse()\nans = 0\ndata.append(0)\nfor i in range(0, n):\n\tif data[i] - data[i + 1] > 0:\n\t\tans += data[i] - data[i + 1]\n\telse:\n\t\tans += 1\n\t\tdata[i + 1] = data[i] - 1\n\t\tif data[i + 1] is 0:\n\t\t\tdata[i + 1] = 1\nprint(suma - ans)\n", "R = lambda : map(int, input().split())\n(n, m) = R()\ni = 0\na = sorted(R())\nfor x in a:\n\ti = min(x, i + 1)\nprint(sum(a) - n - a[-1] + i)\n", "def main():\n\tinl = input().strip().split()\n\t(n, m) = (int(inl[0]), int(inl[1]))\n\tstacks = []\n\ttotal_blocks = 0\n\tfor (i, h) in enumerate(input().strip().split()):\n\t\tstacks.append((i, int(h)))\n\t\ttotal_blocks += int(h)\n\tstacks.sort(key=lambda s: s[1], reverse=True)\n\tblocks = 0\n\thmax = stacks[0][1]\n\tfor i in range(n - 1):\n\t\tc = stacks[i]\n\t\tif c[1] == 0:\n\t\t\tcontinue\n\t\tforced = min(c[1], hmax) - stacks[i + 1][1]\n\t\tif forced > 0:\n\t\t\tblocks += forced\n\t\t\thmax = stacks[i + 1][1]\n\t\telse:\n\t\t\tblocks += 1\n\t\t\thmax -= 1\n\tif stacks[n - 1][1] > 0:\n\t\tif hmax > 0:\n\t\t\tblocks += hmax\n\t\telse:\n\t\t\tblocks += 1\n\tprint(total_blocks - blocks)\nmain()\n", "(n, m) = map(int, input().split())\narr = [int(x) for x in input().split()]\narr = sorted(arr, reverse=True)\narr.append(0)\nisum = sum(arr)\nans = []\ntop = arr[0]\nfor i in range(n):\n\tif arr[i] == 1:\n\t\tans.append(1)\n\t\tarr[i + 1] = 1\n\t\tcontinue\n\tif arr[i + 1] > arr[i]:\n\t\tarr[i + 1] = arr[i]\n\tif arr[i] - arr[i + 1] == 0:\n\t\tans.append(1)\n\t\th = 1\n\telse:\n\t\tans.append(arr[i] - arr[i + 1])\n\t\th = arr[i] - arr[i + 1]\n\ttop = arr[i] - h\n\tarr[i + 1] = top\nprint(isum - sum(ans))\n", "(n, m) = map(int, input().split(' '))\na = list(map(int, input().split(' ')))\na.sort()\ncount = 0\nprev = 0\nfor i in range(n):\n\tcount += 1\n\tif a[i] > prev:\n\t\tprev += 1\ncount += a[n - 1] - prev\nprint(sum(a) - count)\n", "(n, m) = map(int, input().split())\narr = list(map(int, input().split()))\narr.sort()\nans = 0\nheight = 0\nfor i in range(n):\n\tif arr[i] > height:\n\t\tans += 1\n\t\theight += 1\n\telse:\n\t\tans += 1\nif arr[-1] > height:\n\tans += arr[-1] - height\nprint(sum(arr) - ans)\n", "import sys\n(n, m) = list(map(int, input().split()))\nh = list(map(int, input().split()))\ns = sum(h)\nh.sort()\nfor i in range(n - 1, 0, -1):\n\tif h[i] == 1:\n\t\th[i - 1] = 1\n\telif h[i - 1] >= h[i]:\n\t\th[i - 1] = h[i] - 1\nans = 0\nfor i in range(n):\n\tif i == 0:\n\t\tans += h[i]\n\telif h[i] == 1:\n\t\tans += 1\n\telse:\n\t\tans += h[i] - h[i - 1]\nif n == 1:\n\tprint(0)\nelse:\n\tprint(s - ans)\n", "(n, m) = map(int, input().split())\nl = list(map(int, input().split()))\nz = max(l)\nans = 0\nsu = sum(l)\nl.sort()\nh = 0\nfor i in l:\n\tans = ans + i - 1\n\th = min(h + 1, i)\nif h < z:\n\tans = ans - (z - h)\nprint(ans)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.append(0)\na.sort()\nx = 0\nb = 0\nfor i in range(1, n):\n\tif a[i] != b:\n\t\tb += 1\n\tx += 1\nx += a[-1] - b\nif a[-1] - b == 0:\n\tx += 1\nprint(sum(a) - x)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.sort(reverse=True)\nused = a[0]\nf = a[0] - 1\nfor i in range(1, n):\n\tif f > 0:\n\t\tf = min(f - 1, a[i] - 1)\n\telse:\n\t\tused += 1\nprint(sum(a) - used)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.sort()\ncur = 0\nfor i in range(n):\n\tcur = min(cur + 1, a[i])\ncur = a[-1] - cur\nans = sum(a) - n - cur\nprint(ans)\n", "(n, m) = map(int, input().split())\na = sorted(list(map(int, input().split())))[::-1]\ns = sum(a)\nfor i in range(1, n):\n\ta[i] = min(a[i], a[i - 1] - 1)\n\ts -= a[i - 1] - a[i]\nprint(s - max(a[-1], 1))\n", "import math as ma\nimport sys\nfrom sys import exit\nfrom decimal import Decimal as dec\nfrom itertools import permutations\n\ndef li():\n\treturn list(map(int, input().split()))\n\ndef num():\n\treturn map(int, input().split())\n\ndef nu():\n\treturn int(input())\n(n, m) = num()\na = li()\nind = -1\nz = 0\nll = sorted(a)\nmx = ll[n - 1] - 1\ncc = 0\nfor i in range(n - 2, -1, -1):\n\tif ll[i] == 0:\n\t\tcontinue\n\tif mx == 0:\n\t\tcc += ll[i] - 1\n\t\tcontinue\n\tif ll[i] >= mx:\n\t\tcc += 1\n\t\tmx -= 1\n\t\tcc += ll[i] - 1\n\t\tll[i] = 1\n\telse:\n\t\tmx = ll[i]\n\t\tcc += 1\n\t\tmx -= 1\n\t\tcc += ll[i] - 1\n\t\tll[i] = 1\nprint(cc)\n", "import sys\ninput_file = sys.stdin\n[n, m] = list((int(x) for x in input_file.readline().split()))\nstacks = list((int(x) for x in input_file.readline().split()))\nstacks.sort()\nans = 0\ncur_stack = 0\ncur_h = 0\nwhile cur_stack < n:\n\tans += 1\n\tif stacks[cur_stack] >= cur_h + 1:\n\t\tcur_h += 1\n\tcur_stack += 1\nans += stacks[-1] - cur_h\nprint(sum(stacks) - ans)\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.sort()\nres = 0\nsame = 0\np = 1\nfor h in a:\n\tif p <= h:\n\t\tp += 1\n\telse:\n\t\tsame += 1\nres = a[-1] + same\nprint(sum(a) - res)\n", "(n, m) = map(int, input().split())\narr = list(map(int, input().split()))\ns = sum(arr)\narr.sort()\nreq = 0\nprev = 0\nfor i in range(n):\n\treq += 1\n\tif arr[i] > prev:\n\t\tprev += 1\nreq += arr[n - 1] - prev\nprint(s - req)\n", "(n, k) = map(int, input().split())\na = [int(i) for i in input().split()]\na.sort()\nh = a[-1]\nheight = 0\ncount = 0\nfor i in range(n - 1):\n\tif a[i] > height:\n\t\theight = height + 1\n\tcount = count + 1\nif height < h:\n\tprint(sum(a) - (count + h - height))\nelse:\n\tprint(sum(a) - (count + 1))\n", "def func(a, n1):\n\tmaxi = 0\n\tmaxisum1 = 0\n\tif n1 == 1:\n\t\treturn 0\n\tfor i in range(n1 - 1):\n\t\tif a[i] > maxi:\n\t\t\tmaxi += 1\n\t\tmaxisum1 += a[i] - 1\n\tif a[n - 1] == maxi:\n\t\tmaxisum1 += a[i] - 1\n\telse:\n\t\tmaxisum1 += maxi\n\treturn maxisum1\n(n, m) = list(map(int, input().split()))\na = list(map(int, input().rstrip().split()))\na.sort()\nprint(func(a, n))\n", "input()\nA = sorted(list(map(int, input().split())))\nkeep = max(A)\nup_to = 0\nfor a in A:\n\tif a > up_to:\n\t\tup_to += 1\n\telse:\n\t\tkeep += 1\nprint(sum(A) - keep)\n", "(n, _) = map(int, input().split())\na = sorted(map(int, input().split()), reverse=True)\n\ndef solve():\n\tif n == 1:\n\t\treturn 0\n\tret = a[0] - max(a[0] - a[1], 1)\n\tfor i in range(1, n):\n\t\tfromTop = max(0, min(a[i] - a[i - 1] + 1, a[i] - 1))\n\t\ta[i] -= fromTop\n\t\tfromBottom = a[i] - max(1, a[i] - a[i + 1]) if i < n - 1 else 0\n\t\tret += fromTop + fromBottom\n\treturn ret\nprint(solve())\n", "(n, m) = map(int, input().split())\na = list(map(int, input().split()))\na.sort()\nsum1 = sum(a)\ndelete = n\npossible_height = 0\nmax_height = a[n - 1]\nfor i in range(n):\n\tif a[i] > possible_height:\n\t\tpossible_height += 1\nprint(sum1 - delete + possible_height - max_height)\n", "(n, m) = map(int, input().split())\na = [int(o) for o in input().split()]\na = sorted(a)\nb = []\nu = 0\ns = sum(a)\nl = 0\nk = 0\nd = 0\nfor i in range(n):\n\tl = a[i]\n\td += a[i] - u\n\tif d <= i:\n\t\td += 1\n\tu = a[i]\nprint(s - d)\n", "from sys import stdin, stdout\nimport cProfile, math\nfrom collections import Counter\nfrom bisect import bisect_left, bisect, bisect_right\nimport itertools\nfrom copy import deepcopy\nfrom fractions import Fraction\nimport sys, threading\nsys.setrecursionlimit(10 ** 6)\nthreading.stack_size(2 ** 27)\nprintHeap = str()\nmemory_constrained = False\nP = 10 ** 9 + 7\nimport sys\nsys.setrecursionlimit(10000000)\n\nclass Operation:\n\n\tdef __init__(self, name, function, function_on_equal, neutral_value=0):\n\t\tself.name = name\n\t\tself.f = function\n\t\tself.f_on_equal = function_on_equal\n\ndef add_multiple(x, count):\n\treturn x * count\n\ndef min_multiple(x, count):\n\treturn x\n\ndef max_multiple(x, count):\n\treturn x\nsum_operation = Operation('sum', sum, add_multiple, 0)\nmin_operation = Operation('min', min, min_multiple, 1000000000.0)\nmax_operation = Operation('max', max, max_multiple, -1000000000.0)\n\nclass SegmentTree:\n\n\tdef __init__(self, array, operations=[sum_operation, min_operation, max_operation]):\n\t\tself.array = array\n\t\tif type(operations) != list:\n\t\t\traise TypeError('operations must be a list')\n\t\tself.operations = {}\n\t\tfor op in operations:\n\t\t\tself.operations[op.name] = op\n\t\tself.root = SegmentTreeNode(0, len(array) - 1, self)\n\n\tdef query(self, start, end, operation_name):\n\t\tif self.operations.get(operation_name) == None:\n\t\t\traise Exception('This operation is not available')\n\t\treturn self.root._query(start, end, self.operations[operation_name])\n\n\tdef summary(self):\n\t\treturn self.root.values\n\n\tdef update(self, position, value):\n\t\tself.root._update(position, value)\n\n\tdef update_range(self, start, end, value):\n\t\tself.root._update_range(start, end, value)\n\n\tdef __repr__(self):\n\t\treturn self.root.__repr__()\n\nclass SegmentTreeNode:\n\n\tdef __init__(self, start, end, segment_tree):\n\t\tself.range = (start, end)\n\t\tself.parent_tree = segment_tree\n\t\tself.range_value = None\n\t\tself.values = {}\n\t\tself.left = None\n\t\tself.right = None\n\t\tif start == end:\n\t\t\tself._sync()\n\t\t\treturn\n\t\tself.left = SegmentTreeNode(start, start + (end - start) // 2, segment_tree)\n\t\tself.right = SegmentTreeNode(start + (end - start) // 2 + 1, end, segment_tree)\n\t\tself._sync()\n\n\tdef _query(self, start, end, operation):\n\t\tif end < self.range[0] or start > self.range[1]:\n\t\t\treturn None\n\t\tif start <= self.range[0] and self.range[1] <= end:\n\t\t\treturn self.values[operation.name]\n\t\tself._push()\n\t\tleft_res = self.left._query(start, end, operation) if self.left else None\n\t\tright_res = self.right._query(start, end, operation) if self.right else None\n\t\tif left_res is None:\n\t\t\treturn right_res\n\t\tif right_res is None:\n\t\t\treturn left_res\n\t\treturn operation.f([left_res, right_res])\n\n\tdef _update(self, position, value):\n\t\tif position < self.range[0] or position > self.range[1]:\n\t\t\treturn\n\t\tif position == self.range[0] and self.range[1] == position:\n\t\t\tself.parent_tree.array[position] = value\n\t\t\tself._sync()\n\t\t\treturn\n\t\tself._push()\n\t\tself.left._update(position, value)\n\t\tself.right._update(position, value)\n\t\tself._sync()\n\n\tdef _update_range(self, start, end, value):\n\t\tif end < self.range[0] or start > self.range[1]:\n\t\t\treturn\n\t\tif start <= self.range[0] and self.range[1] <= end:\n\t\t\tself.range_value = value\n\t\t\tself._sync()\n\t\t\treturn\n\t\tself._push()\n\t\tself.left._update_range(start, end, value)\n\t\tself.right._update_range(start, end, value)\n\t\tself._sync()\n\n\tdef _sync(self):\n\t\tif self.range[0] == self.range[1]:\n\t\t\tfor op in self.parent_tree.operations.values():\n\t\t\t\tcurrent_value = self.parent_tree.array[self.range[0]]\n\t\t\t\tif self.range_value is not None:\n\t\t\t\t\tcurrent_value = self.range_value\n\t\t\t\tself.values[op.name] = op.f([current_value])\n\t\telse:\n\t\t\tfor op in self.parent_tree.operations.values():\n\t\t\t\tresult = op.f([self.left.values[op.name], self.right.values[op.name]])\n\t\t\t\tif self.range_value is not None:\n\t\t\t\t\tbound_length = self.range[1] - self.range[0] + 1\n\t\t\t\t\tresult = op.f_on_equal(self.range_value, bound_length)\n\t\t\t\tself.values[op.name] = result\n\n\tdef _push(self):\n\t\tif self.range_value is None:\n\t\t\treturn\n\t\tif self.left:\n\t\t\tself.left.range_value = self.range_value\n\t\t\tself.right.range_value = self.range_value\n\t\t\tself.left._sync()\n\t\t\tself.right._sync()\n\t\t\tself.range_value = None\n\n\tdef __repr__(self):\n\t\tans = '({}, {}): {}\\n'.format(self.range[0], self.range[1], self.values)\n\t\tif self.left:\n\t\t\tans += self.left.__repr__()\n\t\tif self.right:\n\t\t\tans += self.right.__repr__()\n\t\treturn ans\n\ndef display(string_to_print):\n\tstdout.write(str(string_to_print) + '\\n')\n\ndef primeFactors(n):\n\tfactors = dict()\n\tfor i in range(2, math.ceil(math.sqrt(n)) + 1):\n\t\twhile n % i == 0:\n\t\t\tif i in factors:\n\t\t\t\tfactors[i] += 1\n\t\t\telse:\n\t\t\t\tfactors[i] = 1\n\t\t\tn = n // i\n\tif n > 2:\n\t\tfactors[n] = 1\n\treturn factors\n\ndef isprime(n):\n\tif n < 4:\n\t\treturn True\n\tif n % 2 == 0:\n\t\treturn False\n\tif n % 3 == 0:\n\t\treturn False\n\ti = 5\n\tw = 2\n\twhile i * i <= n:\n\t\tif n % i == 0:\n\t\t\treturn False\n\t\ti += w\n\t\tw = 6 - w\n\treturn True\n\ndef test_print(*args):\n\tif testingMode:\n\t\tprint(args)\n\ndef display_list(list1, sep=' '):\n\tstdout.write(sep.join(map(str, list1)) + '\\n')\n\ndef get_int():\n\treturn int(stdin.readline().strip())\n\ndef get_tuple():\n\treturn map(int, stdin.readline().split())\n\ndef get_list():\n\treturn list(map(int, stdin.readline().split()))\nmemory = dict()\n\ndef clear_cache():\n\tglobal memory\n\tmemory = dict()\n\ndef cached_fn(fn, *args):\n\tglobal memory\n\tif args in memory:\n\t\treturn memory[args]\n\telse:\n\t\tresult = fn(*args)\n\t\tmemory[args] = result\n\t\treturn result\nTestCases = False\ntestingMode = False\noptimiseForReccursion = False\n\ndef main():\n\t(n, m) = get_tuple()\n\tli = get_list()\n\tres = 0\n\tcurr_height = 1\n\tli.sort()\n\tfor (i, ele) in enumerate(li):\n\t\tif i == len(li) - 1:\n\t\t\tres += curr_height - 1 if curr_height < li[-1] else ele - 1\n\t\telse:\n\t\t\tif ele >= curr_height and curr_height < li[-1]:\n\t\t\t\tcurr_height += 1\n\t\t\tres += ele - 1\n\tprint(res)\nif TestCases:\n\tfor _ in range(get_int()):\n\t\tcProfile.run('main()') if testingMode else main()\nelse:\n\t(cProfile.run('main()') if testingMode else main()) if not optimiseForReccursion else threading.Thread(target=main).start()\n", "import sys\nfrom collections import deque\nimport heapq\ninput = sys.stdin.readline\n(n, m) = map(int, input().split())\narr = list(map(int, input().split()))\narr.sort()\nans = 0\nmaxi = 0\nfor i in range(n):\n\tif arr[i] == 1:\n\t\tmaxi = 1\n\telif arr[i] > maxi:\n\t\tmaxi += 1\n\tans += 1\nans += arr[-1] - maxi\nprint(sum(arr) - ans)\n", "(n, m) = [int(x) for x in input().split()]\nhei = [int(x) for x in input().split()]\ntotal_blocks = 0\nfor x in hei:\n\ttotal_blocks += x\nhei.sort(reverse=True)\nif len(hei) == 1:\n\tprint(0)\n\texit()\nused_blocks = 0\nmax_covered_hei = -1\nfor i in range(len(hei)):\n\tif max_covered_hei == -1:\n\t\tmax_covered_hei = hei[i]\n\t\tused_blocks = 1\n\telse:\n\t\tdiff_to_cur = max(0, max_covered_hei - hei[i])\n\t\tif diff_to_cur == 0:\n\t\t\tused_blocks += 1\n\t\t\tmax_covered_hei -= 1\n\t\t\tmax_covered_hei = max(0, max_covered_hei)\n\t\telse:\n\t\t\tused_blocks += diff_to_cur\n\t\t\tmax_covered_hei = hei[i]\nif max_covered_hei > 1:\n\tused_blocks += max_covered_hei - 1\nprint(total_blocks - used_blocks)\n", "(n, m) = map(int, input().split())\nnum = [int(i) for i in input().split()]\nnum.sort()\nans = n + num[-1]\nc = 0\nfor i in num:\n\tif c < i:\n\t\tc += 1\nprint(sum(num) - ans + c)\n", "(n, m) = map(int, input().split())\na = sorted(list(map(int, input().split())))\nma = a[n - 1]\nyr = 1\ng = 1\nimport sys\nif n == 1:\n\tprint(0)\n\tsys.exit()\nfor i in range(1, n):\n\tif a[i] > yr:\n\t\tyr += 1\n\tg += 1\ng += ma - yr\nprint(sum(a) - g)\n", "(n, k) = map(int, input().split())\na = list(map(int, input().split()))\na.sort()\na = a[::-1]\nsum = int(0)\nmx = int(0)\nfor i in range(n):\n\tsum += a[i]\n\tmx = max(mx, a[i])\nkol = int(0)\nfor i in range(n):\n\tif i != n - 1:\n\t\ta[i + 1] = min(a[i + 1], a[i])\n\t\tif a[i] == a[i + 1] and a[i] != 1:\n\t\t\tmx -= 1\n\t\t\tkol += 1\n\t\ta[i + 1] = min(a[i + 1], mx)\n\t\tif a[i] == 1:\n\t\t\tkol += 1\n\t\telif mx > 1 and mx > a[i + 1]:\n\t\t\tkol += mx - a[i + 1]\n\t\t\tmx -= mx - a[i + 1]\n\telse:\n\t\tkol += a[i]\nans = sum - kol\nprint(ans)\n", "(a, b) = map(int, input().split())\nlist1 = [*map(int, input().split())]\nlist1.sort(reverse=True)\nans = 0\nneededHeight = list1[0]\nfor (i, j) in enumerate(list1[1:]):\n\tneededHeight = max(min(j, list1[i] - 1), 1)\n\tans += j - neededHeight\n\tif list1[i] > 1:\n\t\tans += neededHeight\n\tlist1[i + 1] = neededHeight\nprint(ans)\n", "(N, _) = map(int, input().split())\nA = list(map(int, input().split()))\nA.sort()\nkeep = max(A)\nup_to = 0\nfor i in range(N):\n\tif A[i] > up_to:\n\t\tup_to += 1\n\telse:\n\t\tkeep += 1\nprint(sum(A) - keep)\n", "import math\nfrom typing import Dict, List, Tuple\n\ndef input_lst() -> List[int]:\n\treturn [int(x) for x in input().split()]\n\ndef print_out(res: List[int]):\n\tprint(' '.join([str(x) for x in res]))\n\ndef get_primes(n: int) -> List[int]:\n\tmax_n = n\n\trng = list(range(max_n + 1))\n\trng[0] = 1\n\trng[1] = 1\n\tprimes = []\n\tfor i in range(2, max_n + 1):\n\t\tif rng[i] > 1:\n\t\t\tprimes.append(i)\n\t\t\tfor j in range(i + i, max_n + 1, i):\n\t\t\t\trng[j] = 0\n\treturn primes\n\ndef main():\n\t(n, m) = (int(x) for x in input().split())\n\ta = input_lst()\n\tblock_count = sum(a)\n\tm = max(a)\n\tmin_block_count = n\n\tsorted_a = sorted(a)[::-1]\n\tcur_block_height = m\n\tfor el in sorted_a:\n\t\tif el < cur_block_height:\n\t\t\tmin_block_count += cur_block_height - el\n\t\t\tcur_block_height = el\n\t\tif cur_block_height > 0:\n\t\t\tcur_block_height -= 1\n\tblock_to_delete = block_count - (min_block_count + cur_block_height)\n\tprint(block_to_delete)\nmain()\n", "(n, m) = map(int, input().split())\na = sorted(list(map(int, input().split())))\ntotal = 0\nreq = 0\nans = 0\nprev = 0\nfor i in a:\n\ttotal += i\nfor i in a:\n\treq += 1\n\tif i > prev:\n\t\tprev += 1\nreq += a[-1] - prev\nans = total - req\nprint(ans)\n", "s = input()\ns = s.split()\nfor j in range(len(s)):\n\ts[j] = int(s[j])\nn = s[0]\nm = s[1]\ns1 = input()\ns1 = s1.split()\nfor j in range(n):\n\ts1[j] = int(s1[j])\ns1.sort()\ns1.reverse()\npointer = s1[0]\nres = 0\nflag = 0\nif n == 1:\n\tprint(0)\nelse:\n\tfor i in range(n - 1):\n\t\tif s1[i] != 1:\n\t\t\tif flag == 1:\n\t\t\t\tres = res + s1[i] - 1\n\t\t\telif s1[i] == s1[i + 1]:\n\t\t\t\tpointer = pointer - 1\n\t\t\t\tif pointer == 0:\n\t\t\t\t\tflag = 1\n\t\t\t\t\tpointer = s1[i + 1]\n\t\t\t\tres = res + s1[i] - 1\n\t\t\telif pointer - s1[i + 1] > 1:\n\t\t\t\tres = res + (s1[i] - pointer) + s1[i + 1]\n\t\t\t\tpointer = s1[i + 1]\n\t\t\telse:\n\t\t\t\tpointer = pointer - 1\n\t\t\t\tres = res + s1[i] - 1\n\tif flag == 0:\n\t\tif s1[n - 1] != 1:\n\t\t\tres = res + s1[n - 1] - pointer\n\tif flag == 1:\n\t\tres = res + s1[n - 1] - 1\n\tprint(res)\n", "from collections import defaultdict\n(n, m) = map(int, input().split())\nb = defaultdict(int)\ns = 0\nfor i in input().split():\n\ti = int(i)\n\tb[i] += 1\n\ts += i\na = sorted(b.items(), reverse=True)\np = 0\nq = 0\nd = len(a)\na.append((0, 0))\nfor i in range(d):\n\tl = a[i][0] - a[i + 1][0]\n\tx = a[i][1] + p\n\tif x >= l:\n\t\tp = x - l\n\telse:\n\t\tq = l - x\n\t\tp = 0\ny = a[0][0]\nprint(s - (y + p))\n", "(n, m) = map(int, input().split())\nb = list(map(int, input().split()))\nb.sort()\ntot = 1\nh = 1\nfor i in range(n - 1):\n\tif b[i + 1] > h:\n\t\ttot += 1\n\t\th += 1\n\telse:\n\t\ttot += 1\nprint(sum(b) - (tot + b[-1] - h))\n", "(n, m) = map(int, input().split())\nl = list(map(int, input().split()))\nl.sort(reverse=True)\nsa = sum(l)\nt = 0\nfor i in range(len(l) - 1):\n\tif l[i] != 1:\n\t\tif l[i] > l[i + 1]:\n\t\t\tt += l[i] - l[i + 1]\n\t\telif l[i] == l[i + 1]:\n\t\t\tl[i + 1] -= 1\n\t\t\tt += 1\n\t\telse:\n\t\t\tl[i + 1] = l[i] - 1\n\t\t\tt += 1\n\telse:\n\t\tt += len(l) - 1 - i\n\t\tl[-1] = 1\n\t\tbreak\nt += l[-1]\nprint(sa - t)\n", "(n, m) = map(int, input().split())\ninp = list(map(int, input().split()))\ninp.sort()\npos = 1\nfor i in inp[0:n - 1]:\n\tif pos == inp[n - 1]:\n\t\tbreak\n\telif i >= pos:\n\t\tpos += 1\nprint(sum(inp) - (n - 1) - (inp[n - 1] - pos + 1))\n", "from sys import stdin\nfrom collections import deque\nmod = 10 ** 9 + 7\nimport sys\nfrom bisect import bisect_right\nfrom bisect import bisect_left\nfrom collections import defaultdict\nfrom math import sqrt, factorial, gcd, log2, inf, ceil\nimport heapq\ninput = lambda : sys.stdin.readline().rstrip()\nfrom sys import stdin, stdout\nfrom heapq import heapify, heappush, heappop\n(n, m) = map(int, input().split())\nl = list(map(int, input().split()))\nl.sort(reverse=True)\nans = 0\ncnt = 0\nhash = defaultdict(int)\nflag = 1\nfor i in range(1, n):\n\tans += l[i] - 1\n\thash[l[i]] += 1\n\tif hash[l[i]] < l[i] and flag and (cnt < l[0]):\n\t\tcnt += 1\n\tif hash[l[i]] == l[i] and flag and (cnt < l[0]):\n\t\tflag = 0\n\t\tcnt += 1\nif cnt == l[0]:\n\tcnt -= 1\nprint(ans + cnt)\n"]

difficulty: MEDIUM

source: codeforces

raw_problem:
B. Views Matter

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

You came to the exhibition and one exhibit has drawn your attention. It consists of $$$n$$$ stacks of blocks, where the $$$i$$$-th stack consists of $$$a_i$$$ blocks resting on the surface.

The height of the exhibit is equal to $$$m$$$. Consequently, the number of blocks in each stack is less than or equal to $$$m$$$.

There is a camera on the ceiling that sees the top view of the blocks and a camera on the right wall that sees the side view of the blocks.

Find the maximum number of blocks you can remove such that the views for both the cameras would not change.

Note, that while originally all blocks are stacked on the floor, it is not required for them to stay connected to the floor after some blocks are removed. There is no gravity in the whole exhibition, so no block would fall down, even if the block underneath is removed. It is not allowed to move blocks by hand either.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le m \le 10^9$$$) — the number of stacks and the height of the exhibit.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — the number of blocks in each stack from left to right.

Output

Print exactly one integer — the maximum number of blocks that can be removed.

Examples

Input

5 6
3 3 3 3 3

Output

10

Input

3 5
1 2 4

Output

3

Input

5 5
2 3 1 4 4

Output

9

Input

1 1000
548

Output

0

Input

3 3
3 1 1

Output

1

Note

The following pictures illustrate the first example and its possible solution.

Blue cells indicate removed blocks. There are $$$10$$$ blue cells, so the answer is $$$10$$$.

question:
You came to the exhibition and one exhibit has drawn your attention. It consists of $$$n$$$ stacks of blocks, where the $$$i$$$-th stack consists of $$$a_i$$$ blocks resting on the surface.
The height of the exhibit is equal to $$$m$$$. Consequently, the number of blocks in each stack is less than or equal to $$$m$$$.
There is a camera on the ceiling that sees the top view of the blocks and a camera on the right wall that sees the side view of the blocks.
![image](1.png) Find the maximum number of blocks you can remove such that the views for both the cameras would not change.
Note, that while originally all blocks are stacked on the floor, it is not required for them to stay connected to the floor after some blocks are removed. There is no gravity in the whole exhibition, so no block would fall down, even if the block underneath is removed. It is not allowed to move blocks by hand either.

Input
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le m \le 10^9$$$) — the number of stacks and the height of the exhibit.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — the number of blocks in each stack from left to right.

Output
Print exactly one integer — the maximum number of blocks that can be removed.

Examples
Input
5 6
3 3 3 3 3

Output
10

Input
3 5
1 2 4

Output
3

Input
5 5
2 3 1 4 4

Output
9

Input
1 1000
548

Output
0

Input
3 3
3 1 1

Output
1

Note
The following pictures illustrate the first example and its possible solution.
Blue cells indicate removed blocks. There are $$$10$$$ blue cells, so the answer is $$$10$$$.
![image](2.png)

tags: ['Sorting', 'Implementation', 'Greedy algorithms']

skill_types: ['Sorting', 'Greedy algorithms']

Expected Time Complexity: O(NLOG(N))

image_tags:
3D Geometry
3D Geometry

data_split: test


A. Easy As ABC

problem_raw:
A. Easy As ABC

time limit per test
1 second

memory limit per test
1024 megabytes

input
standard input

output
standard output

You are playing a word puzzle. The puzzle starts with a $$$3$$$ by $$$3$$$ grid, where each cell contains either the letter A, B, or C.

The goal of this puzzle is to find the lexicographically smallest possible word of length $$$3$$$. The word can be formed by choosing three different cells where the cell containing the first letter is adjacent to the cell containing the second letter, and the cell containing the second letter is adjacent to the cell containing the third letter.

Two cells are adjacent to each other if they share a border or a corner, as shown in the following illustration. Formally, if $$$(r, c)$$$ denotes the cell in the $$$r$$$-th row and $$$c$$$-th column, then cell $$$(r, c)$$$ is adjacent to cell $$$(r, c + 1)$$$, $$$(r - 1, c + 1)$$$, $$$(r - 1, c)$$$, $$$(r - 1, c - 1)$$$, $$$(r, c - 1)$$$, $$$(r + 1, c - 1)$$$, $$$(r + 1, c)$$$, and $$$(r + 1, c + 1)$$$.

Determine the lexicographically smallest possible word of length $$$3$$$ that you can find within the grid.

A string $$$s$$$ of length $$$n$$$ is lexicographically smaller than string $$$t$$$ of the same length if there exists an integer $$$1 \leq i \leq n$$$ such that $$$s_j = t_j$$$ for all $$$1 \leq j < i$$$, and $$$s_i < t_i$$$ in alphabetical order. The following illustration shows some examples on some grids and their the lexicographically smallest possible word of length $$$3$$$ that you can find within the grids.

Input

Input consists of three lines, each containing three letters, representing the puzzle grid. Each letter in the grid can only be either A, B, or C.

Output

Output the lexicographically smallest possible word of length $$$3$$$ that you can find within the grid.

Examples

Input

BCB
CAC
BCB

Output

ABC

Input

BCB
CCC
CCA

Output

ACB

Input

ACA
CBC
ACA

Output

ABA

Input

ACA
CAC
ACA

Output

AAA

Input

CCC
CBC
CCC

Output

BCC

problem_index: A

time_limit: 1 second

memory_limit: 1024 megabytes

input:
BCB
CAC
BCB

output: ABC

input:
BCB
CCC
CCA

output: ACB

input:
ACA
CBC
ACA

output: ABA

input:
ACA
CAC
ACA

output: AAA

input:
CCC
CBC
CCC

output: BCC

input_output: {"inputs": ["BCB\r\nCAC\r\nBCB\r\n", "BCB\r\nCCC\r\nCCA\r\n", "ACA\r\nCBC\r\nACA\r\n", "ACA\r\nCAC\r\nACA\r\n", "CCC\r\nCBC\r\nCCC\r\n", "CCC\r\nCAC\r\nCCC\r\n", "CCA\r\nACC\r\nCAC\r\n", "CCC\r\nCCC\r\nCBA\r\n", "CCA\r\nCCC\r\nBCC\r\n", "BCC\r\nCCC\r\nCCA\r\n", "CCB\r\nCCC\r\nACC\r\n", "ACC\r\nCCC\r\nCCB\r\n", "ACB\r\nCCC\r\nBCA\r\n", "ACB\r\nCCC\r\nCBA\r\n", "ACC\r\nCCB\r\nCBA\r\n", "ACC\r\nCCC\r\nCBA\r\n", "AAA\r\nAAA\r\nAAA\r\n", "BBB\r\nBBB\r\nBBB\r\n", "CCC\r\nCCC\r\nCCC\r\n", "ABB\r\nBBB\r\nBBC\r\n", "BCB\r\nCCC\r\nBCB\r\n", "BCB\r\nCCC\r\nBBC\r\n", "BCC\r\nCCB\r\nCCB\r\n", "CCC\r\nCBC\r\nCCB\r\n", "BBA\r\nBBB\r\nCBB\r\n", "ACA\r\nCCC\r\nACA\r\n", "CCC\r\nCCC\r\nCCA\r\n", "BBB\r\nBAB\r\nBBB\r\n", "CBB\r\nBBB\r\nBBA\r\n", "BBC\r\nBBB\r\nABB\r\n", "ABC\r\nBCA\r\nCAB\r\n", "ABC\r\nCAB\r\nBCA\r\n", "ACB\r\nCBA\r\nBAC\r\n", "ACB\r\nBAC\r\nCBA\r\n", "BAC\r\nACB\r\nCBA\r\n", "BAC\r\nCBA\r\nACB\r\n", "BCA\r\nCAB\r\nABC\r\n", "BCA\r\nABC\r\nCAB\r\n", "CAB\r\nABC\r\nBCA\r\n", "CAB\r\nBCA\r\nABC\r\n", "CBA\r\nBAC\r\nACB\r\n", "CBA\r\nACB\r\nBAC\r\n", "ABC\r\nBCB\r\nCBA\r\n", "CBA\r\nBCB\r\nABC\r\n", "BAB\r\nACA\r\nBAB\r\n", "ABA\r\nBCB\r\nABA\r\n", "CBA\r\nABC\r\nCBA\r\n", "BCB\r\nCAC\r\nCBC\r\n", "CBA\r\nCBA\r\nCBA\r\n", "CCC\r\nBBB\r\nAAA\r\n", "ABC\r\nABC\r\nABC\r\n", "BBB\r\nAAA\r\nCCC\r\n", "ABC\r\nBBC\r\nCCA\r\n", "CAA\r\nAAA\r\nABC\r\n", "ABC\r\nCCC\r\nCBB\r\n"], "outputs": ["ABC\r\n", "ACB\r\n", "ABA\r\n", "AAA\r\n", "BCC\r\n", "ACC\r\n", "AAC\r\n", "ABC\r\n", "ACB\r\n", "ACB\r\n", "ACB\r\n", "ACB\r\n", "ACA\r\n", "ABC\r\n", "ABB\r\n", "ABC\r\n", "AAA\r\n", "BBB\r\n", "CCC\r\n", "ABB\r\n", "BCB\r\n", "BBC\r\n", "BBC\r\n", "BBC\r\n", "ABB\r\n", "ACA\r\n", "ACC\r\n", "ABB\r\n", "ABB\r\n", "ABB\r\n", "AAB\r\n", "AAA\r\n", "AAB\r\n", "AAA\r\n", "AAB\r\n", "AAB\r\n", "AAA\r\n", "AAB\r\n", "AAB\r\n", "AAB\r\n", "AAA\r\n", "AAB\r\n", "ABB\r\n", "ABB\r\n", "AAA\r\n", "ABA\r\n", "ABA\r\n", "ABC\r\n", "AAA\r\n", "AAA\r\n", "AAA\r\n", "AAA\r\n", "ABA\r\n", "AAA\r\n", "ABC\r\n"]}

question:
You are playing a word puzzle. The puzzle starts with a $$$3$$$ by $$$3$$$ grid, where each cell contains either the letter A, B, or C.
The goal of this puzzle is to find the lexicographically smallest possible word of length $$$3$$$. The word can be formed by choosing three different cells where the cell containing the first letter is adjacent to the cell containing the second letter, and the cell containing the second letter is adjacent to the cell containing the third letter.
Two cells are adjacent to each other if they share a border or a corner, as shown in the following illustration. Formally, if $$$(r, c)$$$ denotes the cell in the $$$r$$$-th row and $$$c$$$-th column, then cell $$$(r, c)$$$ is adjacent to cell $$$(r, c + 1)$$$, $$$(r - 1, c + 1)$$$, $$$(r - 1, c)$$$, $$$(r - 1, c - 1)$$$, $$$(r, c - 1)$$$, $$$(r + 1, c - 1)$$$, $$$(r + 1, c)$$$, and $$$(r + 1, c + 1)$$$.
 ![image](1.png) Determine the lexicographically smallest possible word of length $$$3$$$ that you can find within the grid.
A string $$$s$$$ of length $$$n$$$ is lexicographically smaller than string $$$t$$$ of the same length if there exists an integer $$$1 \leq i \leq n$$$ such that $$$s_j = t_j$$$ for all $$$1 \leq j < i$$$, and $$$s_i < t_i$$$ in alphabetical order. The following illustration shows some examples on some grids and their the lexicographically smallest possible word of length $$$3$$$ that you can find within the grids.
 ![image](2.png)
Input
Input consists of three lines, each containing three letters, representing the puzzle grid. Each letter in the grid can only be either A, B, or C.

Output
Output the lexicographically smallest possible word of length $$$3$$$ that you can find within the grid.

Examples
Input

BCB
CAC
BCB

Output

ABC

Input

BCB
CCC
CCA

Output

ACB

Input

ACA
CBC
ACA

Output

ABA

Input

ACA
CAC
ACA

Output

AAA

Input

CCC
CBC
CCC

Output

BCC

source: codeforces

image_tags: Patterns Patterns

data_split: test