# paiza POH! Vol.1
# result:
# http://p...content-available-to-author-only...a.jp/poh/ec-campaign/result/dcb4fefe9a664bb385df949cf057122e
# author: Leonardone @ NEETSDKASU
def foo(p, f, e, m)
df = e - f
if df < 5 then
f
else
ci = f + (df >> 1)
if m > p[ci] then
foo(p, ci, e, m)
else
foo(p, f, ci, m)
end
end
end
def bar(p, f, e, m)
df = e - f
if df < 5 then
e
else
ci = f + (df >> 1)
if m < p[ci] then
bar(p, f, ci, m)
else
bar(p, ci, e, m)
end
end
end
s = gets.split(' ')
n = s[0].to_i
d = s[1].to_i
p = []
n.times do |i|
p[i] = gets.to_i
end
p = p.sort
d.times do
m = gets.to_i
tmp = 0
j = bar(p, 0, n - 1, m)
while (j >= 0) && (p[j] >= m) do
j = j - 1
end
if j >=0 then
df = m - p[j]
if df <= p[j] then
i = foo(p, 0, j, df)
while df <= p[j] do
while (df > p[i]) do
i = i + 1
end
if (df < p[i]) || (i == j) then
if i > 0 then
i = i - 1
end
end
sum = p[i] + p[j]
if (sum > tmp) && (sum <= m) then
tmp = sum
if tmp == m then
break
end
end
j = j - 1
df = m - p[j]
end
end
end
puts tmp
end
IyBwYWl6YSBQT0ghIFZvbC4xCiMgcmVzdWx0OgojIGh0dHA6Ly9wLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5hLmpwL3BvaC9lYy1jYW1wYWlnbi9yZXN1bHQvZGNiNGZlZmU5YTY2NGJiMzg1ZGY5NDljZjA1NzEyMmUKIyBhdXRob3I6IExlb25hcmRvbmUgQCBORUVUU0RLQVNVCgpkZWYgZm9vKHAsIGYsIGUsIG0pCglkZiA9IGUgLSBmCglpZiBkZiA8IDUgdGhlbgoJCWYKCWVsc2UKCQljaSA9IGYgKyAoZGYgPj4gMSkKCQlpZiBtID4gcFtjaV0gdGhlbgoJCQlmb28ocCwgY2ksIGUsIG0pCgkJZWxzZQoJCQlmb28ocCwgZiwgY2ksIG0pCgkJZW5kCgllbmQKZW5kCgpkZWYgYmFyKHAsIGYsIGUsIG0pIAoJZGYgPSBlIC0gZgoJaWYgZGYgPCA1IHRoZW4KCQllCgllbHNlCgkJY2kgPSBmICsgKGRmID4+IDEpCgkJaWYgbSA8IHBbY2ldIHRoZW4KCQkJYmFyKHAsIGYsIGNpLCBtKQoJCWVsc2UKCQkJYmFyKHAsIGNpLCBlLCBtKQoJCWVuZAoJZW5kCmVuZAoJCgpzID0gZ2V0cy5zcGxpdCgnICcpCm4gPSBzWzBdLnRvX2kKZCA9IHNbMV0udG9faQpwID0gW10Kbi50aW1lcyBkbyB8aXwKCXBbaV0gPSBnZXRzLnRvX2kKZW5kCnAgPSBwLnNvcnQKCmQudGltZXMgZG8KCW0gPSBnZXRzLnRvX2kKCXRtcCA9IDAKCWogPSBiYXIocCwgMCwgbiAtIDEsIG0pCgl3aGlsZSAoaiA+PSAwKSAmJiAocFtqXSA+PSBtKSBkbwoJCWogPSBqIC0gMQoJZW5kCglpZiBqID49MCB0aGVuCgkJZGYgPSBtIC0gcFtqXQoJCWlmIGRmIDw9IHBbal0gdGhlbgoJCQlpID0gZm9vKHAsIDAsIGosIGRmKQoJCQl3aGlsZSBkZiA8PSBwW2pdIGRvCgkJCQl3aGlsZSAoZGYgPiBwW2ldKSBkbwoJCQkJCWkgPSBpICsgMQoJCQkJZW5kCgkJCQlpZiAoZGYgPCBwW2ldKSB8fCAoaSA9PSBqKSB0aGVuCgkJCQkJaWYgaSA+IDAgdGhlbgoJCQkJCQlpID0gaSAtIDEKCQkJCQllbmQKCQkJCWVuZAoJCQkJc3VtID0gcFtpXSArIHBbal0KCQkJCWlmIChzdW0gPiB0bXApICYmIChzdW0gPD0gbSkgdGhlbgoJCQkJCXRtcCA9IHN1bQoJCQkJCWlmIHRtcCA9PSBtIHRoZW4KCQkJCQkJYnJlYWsKCQkJCQllbmQKCQkJCWVuZAoJCQkJaiA9IGogLSAxCgkJCQlkZiA9IG0gLSBwW2pdCgkJCWVuZAoJCWVuZAoJZW5kCglwdXRzIHRtcAplbmQ=