'Jeopardy!' is an intellectual game where players answer questions and earn points. Company Q conducts a simplified 'Jeopardy!' tournament among the best IT companies. By a lucky coincidence, the old rivals made it to the finals: company R1 and company R2. 

The finals will have n questions, m of them are auction questions and n - m of them are regular questions. Each question has a price. The price of the i-th question is a_{i} points. During the game the players chose the questions. At that, if the question is an auction, then the player who chose it can change the price if the number of his current points is strictly larger than the price of the question. The new price of the question cannot be less than the original price and cannot be greater than the current number of points of the player who chose the question. The correct answer brings the player the points equal to the price of the question. The wrong answer to the question reduces the number of the player's points by the value of the question price.

The game will go as follows. First, the R2 company selects a question, then the questions are chosen by the one who answered the previous question correctly. If no one answered the question, then the person who chose last chooses again.

All R2 employees support their team. They want to calculate what maximum possible number of points the R2 team can get if luck is on their side during the whole game (they will always be the first to correctly answer questions). Perhaps you are not going to be surprised, but this problem was again entrusted for you to solve.


-----Input-----

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 100; m ≤ min(n, 30)) — the total number of questions and the number of auction questions, correspondingly. The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^7) — the prices of the questions. The third line contains m distinct integers b_{i} (1 ≤ b_{i} ≤ n) — the numbers of auction questions. Assume that the questions are numbered from 1 to n.


-----Output-----

In the single line, print the answer to the problem — the maximum points the R2 company can get if it plays optimally well. It is guaranteed that the answer fits into the integer 64-bit signed type.


-----Examples-----
Input
4 1
1 3 7 5
3

Output
18

Input
3 2
10 3 8
2 3

Output
40

Input
2 2
100 200
1 2

Output
400

Source: codeforces | Difficulty: MEDIUM
Tags: Mathematics

Greedy algorithms


Solutions:
from collections import deque as de
import math
from math import sqrt as sq
from math import floor as fl
from math import ceil as ce
from sys import stdin, stdout
import re
from collections import Counter as cnt
from functools import reduce
from itertools import groupby as gb
from bisect import bisect_left as bl, bisect_right as br

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

class My_stack:

	def __init__(self):
		self.data = []

	def my_push(self, x):
		return self.data.append(x)

	def my_pop(self):
		return self.data.pop()

	def my_peak(self):
		return self.data[-1]

	def my_contains(self, x):
		return self.data.count(x)

	def my_show_all(self):
		return self.data

	def isEmpty(self):
		return len(self.data) == 0
arrStack = My_stack()

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def binarytodecimal(n):
	return int(n, 2)

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def get_prime_factors(number):
	prime_factors = []
	while number % 2 == 0:
		prime_factors.append(2)
		number = number / 2
	for i in range(3, int(math.sqrt(number)) + 1, 2):
		while number % i == 0:
			prime_factors.append(int(i))
			number = number / i
	if number > 2:
		prime_factors.append(int(number))
	return prime_factors

def get_frequency(list):
	dic = {}
	for ele in list:
		if ele in dic:
			dic[ele] += 1
		else:
			dic[ele] = 1
	return dic

def Log2(x):
	return math.log10(x) / math.log10(2)

def getProduct(n):
	product = 1
	while n != 0:
		product = product * (n % 10)
		n = n // 10
	return product

def lcm(x, y):
	lcm = x * y // math.gcd(x, y)
	return lcm

def isPowerOfTwo(n):
	return math.ceil(Log2(n)) == math.floor(Log2(n))

def checkisap(list):
	d = list[1] - list[0]
	for i in range(2, len(list)):
		temp = list[i] - list[i - 1]
		if temp != d:
			return False
	return True

def primes_method5(n):
	out = {}
	sieve = [True] * (n + 1)
	for p in range(2, n + 1):
		if sieve[p]:
			out[p] = 1
			for i in range(p, n + 1, p):
				sieve[i] = False
	return out

def getSum(n):
	strr = str(n)
	list_of_number = list(map(int, strr.strip()))
	return sum(list_of_number)

def ceildiv(x, y):
	return (x + y - 1) // y

def di():
	return map(int, input().split())

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def si():
	return list(map(str, input()))

def indict():
	dic = {}
	for (index, value) in enumerate(input().split()):
		dic[int(value)] = int(index) + 1
	return dic

def frqdict():
	dic = {}
	for (index, value) in enumerate(input()):
		if value not in dic:
			dic[value] = 1
		else:
			dic[value] += 1
	return dic
(n, m) = di()
a = li()
b = indict()
if n - m == 0:
	mx = max(a)
	ind = a.index(mx)
	for i in range(n):
		if i != ind:
			mx += max(a[i], mx)
	print(mx)
else:
	ans = 0
	temp = []
	for i in range(n):
		if i + 1 not in b:
			ans += a[i]
		else:
			temp.append(a[i])
	temp.sort(reverse=True)
	for ele in temp:
		ans += max(ele, ans)
	print(ans)


(n, m) = tuple(map(int, str.split(input())))
a = tuple(map(int, str.split(input())))
mi = tuple(map(int, str.split(input())))
ms = sorted(map(lambda i: a[i - 1], mi), reverse=True)
points = 0
for (i, ai) in enumerate(a):
	if i + 1 not in mi:
		points += ai
for m in ms:
	if m > points:
		points += m
	else:
		points += points
print(points)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = [a[i - 1] for i in map(int, input().split())]
b.sort(reverse=True)
s = sum(a) - sum(b)
for i in b:
	s += s if i < s else i
print(s)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz/'
M = 1000000007
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, m) = value()
a = array()
have = set(array())
need = []
ans = 0
for i in range(n):
	if i + 1 not in have:
		ans += a[i]
	else:
		need.append(a[i])
need.sort(reverse=True)
for i in need:
	if ans <= i:
		ans += i
	else:
		ans *= 2
print(ans)


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
arr1 = list(map(int, input().split()))
a = []
ans = 0
for i in range(n):
	if i + 1 in arr1:
		a.append(arr[i])
	else:
		ans += arr[i]
a = sorted(a)[::-1]
for i in range(m):
	if ans > a[i]:
		ans += ans
	else:
		ans += a[i]
print(ans)


(n, m) = map(int, input().split())
que = list(map(int, input().split()))
auc = list(map(int, input().split()))
s = sum(que)
aa = []
for i in auc:
	s -= que[i - 1]
	aa.append(que[i - 1])
aa.sort()
for i in aa[::-1]:
	if i < s:
		s *= 2
	else:
		s += i
print(s)


import bisect
from itertools import accumulate, count
import os
import sys
import math
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
r2 = 0
a = [0] + a
auction = []
for i in range(0, len(b)):
	auction.append(a[b[i]])
	a[b[i]] = -1
for i in range(1, len(a)):
	if a[i] != -1:
		r2 += a[i]
r1 = r2
auction.sort()
for i in range(0, len(auction)):
	if auction[i] < r2:
		r2 = r2 * 2
	else:
		r2 += auction[i]
for i in range(len(auction) - 1, -1, -1):
	if auction[i] < r1:
		r1 += r1
	else:
		r1 += auction[i]
print(max(r2, r1))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
ans = 0
for i in range(m):
	ans -= a[b[i] - 1]
	c.append(a[b[i] - 1])
ans += sum(a)
c.sort()
c = c[::-1]
mx = ans
for i in range(m + 1):
	x = (sum(c[:i]) + ans) * 2 ** (m - i)
	if x > mx:
		mx = x
print(mx)


R = lambda : map(int, input().split())
(n, m) = R()
a = list(R())
b = list(R())
li = []
cost = 0
for i in range(1, n + 1):
	if i not in b:
		cost += a[i - 1]
	else:
		li.append(a[i - 1])
li.sort(reverse=True)
for i in range(m):
	cost += max(cost, li[i])
print(cost)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
mm = list(map(int, input().split()))
s = 0
a = []
for i in range(0, n):
	if i + 1 not in mm:
		s += l[i]
for i in range(0, m):
	v = l[mm[i] - 1]
	a.append(v)
a.sort(reverse=True)
for i in a:
	if s >= i:
		s += s
	else:
		s += i
print(s)


from operator import itemgetter
R = lambda : map(int, input().split())
(n, m) = R()
a = list(R())
b = [0] * n
for i in R():
	b[i - 1] = 1
a = sorted(enumerate(a), key=itemgetter(1), reverse=True)
s = sum((x for (i, x) in a if b[i] != 1))
for (i, x) in a:
	if b[i] == 1:
		s += s if s > x else x
print(s)


(n, m) = map(int, input().split())
ques = list(map(int, input().split()))
acutions = set(map(int, input().split()))
acu = []
points = 0
for i in range(n):
	if i + 1 in acutions:
		acu.append(ques[i])
	else:
		points += ques[i]
acu.sort(reverse=True)
for a in acu:
	if points > a:
		points += points
	else:
		points += a
print(points)


import sys
from itertools import *
from math import *
MAX = 10000000

def solve():
	(n, m) = list(map(int, input().split()))
	quest = list(map(int, input().split()))
	auctindex = set(map(int, input().split()))
	aucts = list()
	firstsum = 0
	for (i, q) in enumerate(quest):
		if i + 1 not in auctindex:
			firstsum += q
		else:
			aucts.append(q)
	aucts.sort(reverse=True)
	for val in aucts:
		firstsum += max(firstsum, val)
	print(firstsum)
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
solve()


import sys

def main():
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	auction_questions = set(map(int, input().split()))
	regular_a = [a[i] for i in range(len(a)) if i + 1 not in auction_questions]
	auction_a = [a[i] for i in range(len(a)) if i + 1 in auction_questions]
	total_points = sum(regular_a)
	auction_a.sort(reverse=True)
	for a in auction_a:
		if a < total_points:
			total_points += total_points
		else:
			total_points += a
	print(total_points)

def __starting_point():
	main()
__starting_point()


(n, m) = list(map(int, input().split()))
lst = list(map(int, input().split()))
au = list(map(int, input().split()))
res = sum(lst)
ls = []
for i in range(m):
	res -= lst[au[i] - 1]
	ls.append(lst[au[i] - 1])
ls.sort(reverse=True)
for i in range(len(ls)):
	res += max(ls[i], res)
print(res)


(n, m) = map(int, input().split(' '))
tmp = list(map(int, input().split(' ')))
m_nums = list(map(lambda x: int(x) - 1, input().split(' ')))
m_list = [tmp[el] for el in m_nums]
_sum = sum(tmp) - sum(m_list)
m_list.sort()
while m_list and m_list[len(m_list) - 1] > _sum:
	_sum += m_list.pop()
print(_sum * 2 ** len(m_list))


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
mm = list(map(int, input().split()))
ans = 0
a = []
for i in range(0, n):
	if i + 1 not in mm:
		ans += l[i]
for i in range(0, m):
	v = l[mm[i] - 1]
	a.append(v)
a = sorted(a)[::-1]
for i in a:
	if ans >= i:
		ans += ans
	else:
		ans += i
print(ans)


(n, m) = map(int, input().split())
prices = list(map(int, input().split()))
normal = []
auct = []
q = list(map(int, input().split()))
sum = 0
for i in range(n):
	if i + 1 in q:
		auct.append(prices[i])
	else:
		sum += prices[i]
auct = sorted(auct, reverse=True)
for elem in auct:
	sum += max(elem, sum)
print(sum)


([n, m], q, a) = (map(int, input().split()), list(map(int, input().split())), list(map(int, input().split())))
ans = sum((q[x - 1] for x in set(range(1, n + 1)) - set(a)))
for x in sorted(a, key=lambda x: q[x - 1], reverse=True):
	if q[x - 1] <= ans:
		ans <<= 1
	else:
		ans += q[x - 1]
print(ans)


(n, m) = list(map(int, input().split()))
inp = list(map(int, input().split()))
vals = list(map(int, input().split()))
aps = []
nps = []
for i in range(n):
	if i + 1 in vals:
		aps.append(inp[i])
	else:
		nps.append(inp[i])
aps = sorted(aps, reverse=True)
ans = sum(nps)
for x in aps:
	if x < ans:
		ans += ans
	else:
		ans += x
print(ans)


(n, m) = list(map(int, input().split()))
prices = list(map(int, input().split()))
auci = list(map(int, input().split()))
scores = 0
for i in range(len(prices)):
	if i + 1 not in auci:
		scores += prices[i]
		prices[i] = 0
ra = []
for i in prices:
	if i != 0:
		ra.append(i)
ra.sort()
ra = ra[::-1]
for i in ra:
	if i > scores:
		scores += i
	else:
		scores *= 2
print(scores)


(n, m) = map(int, input().split())
mat = list(map(int, input().split()))
auction = list(map(int, input().split()))
aucpoint = [mat[i - 1] for i in auction]
aucpoint.sort(reverse=True)
for i in auction:
	mat[i - 1] = 0
s = sum(mat)
for point in aucpoint:
	if s > point:
		s *= 2
	else:
		s += point
print(s)


a = lambda : list(map(int, input().split()))
(n, m) = a()
sa = a()
sb = a()
au = []
for i in reversed(sorted(sb)):
	au.append(sa.pop(i - 1))
su = sum(sa)
au.sort(reverse=True)
for i in range(m):
	t = au.pop(0)
	if t > su:
		su += t
	else:
		su *= 2
print(su)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for i in range(m):
	k = a[b[i] - 1]
	a[b[i] - 1] = 0
	b[i] = k
s = sum(a)
b.sort()
for i in range(m - 1, -1, -1):
	if s >= b[i]:
		s += s
	else:
		s += b[i]
print(s)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
nums = set(list(map(int, input().split())))
stan = []
auct = []
for i in range(len(a)):
	if i + 1 not in nums:
		stan.append(a[i])
	else:
		auct.append(a[i])
sm = sum(stan)
auct = list(reversed(sorted(auct)))
for i in range(len(auct)):
	if sm >= auct[i]:
		if sm > auct[i]:
			sm *= 2
		else:
			sm += auct[i]
	else:
		sm += auct[i]
print(sm)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for i in range(len(b)):
	b[i] -= 1
b = set(b)
c = []
d = []
for i in range(len(a)):
	if i in b:
		c.append(a[i])
	else:
		d.append(a[i])
sum = 0
for i in range(len(d)):
	sum += d[i]
c = sorted(c)
if sum < c[-1]:
	sum += c[-1]
	sum *= 2 ** (len(c) - 1)
else:
	sum *= 2 ** len(c)
print(sum)