46 lines
1 KiB
Python
46 lines
1 KiB
Python
from __future__ import print_function
|
|
import sys, math
|
|
|
|
def val(c,f,u):
|
|
a, b = c - min(c, f), f - min(c, f)
|
|
if u > b - a:
|
|
return b + (lambda x: x//2+1 if x%2==0 and x!=0 else int(math.ceil(x/2.0)))(u - b)
|
|
else:
|
|
return None
|
|
|
|
s = int(sys.stdin.readline())
|
|
D = []
|
|
n = 0
|
|
|
|
for d,c,f,u in ( map(int, line.split()) for line in sys.stdin ):
|
|
n += d; x = val(c,f,u)
|
|
if x is not None: D.append((d,x))
|
|
|
|
# print(D)
|
|
|
|
m = n//2+1
|
|
C = [ [0,set()] for i in xrange(n+1) ]
|
|
|
|
for i in xrange(n+1):
|
|
xs = [ (C[i-D[j][0]], j, D[j][1]) for j in xrange(len(D))
|
|
if D[j][0] <= i and j not in C[i-D[j][0]][1] ]
|
|
# print("i = ", i, " xs = ", xs)
|
|
if xs:
|
|
c, j, cost = min(xs, key = lambda x: x[2])
|
|
C[i] = c[:]
|
|
C[i][0] += cost
|
|
C[i][1] = C[i][1].copy(); C[i][1].add(j)
|
|
else:
|
|
C[i] = C[i-1]
|
|
# print(C[i])
|
|
|
|
# print(m, n)
|
|
# for c in C: print(c)
|
|
|
|
for i in xrange(n+1):
|
|
cost, delegates = sum( D[j][1] for j in C[i][1] ), sum( D[j][0] for j in C[i][1] )
|
|
if delegates >= m:
|
|
print(cost)
|
|
sys.exit(0)
|
|
print("impossible")
|