import heapq
import sys
N=int(sys.stdin.readline())
lst=[]
csm=0
for i in range(N):
  f,t=map(int,sys.stdin.readline().split())
  lst.append([t,f])
  csm=max(csm,f)
lst.sort(reverse=True)

INF=1<<62
dp=[[INF]*(csm+1) for _ in range(N+1)]
dp[0][0] = 0

FPT=16
MSK=(1<<FPT)-1
for i in range(N):
  t,f=lst[i]
  dst=[[] for _ in range(2)]
  for j in range(csm+1):
    start=j-f
    takeoff=dp[i][j]
    if takeoff<INF:
      if start<0:
        start=-start
        takeoff+=start*t  
      stop=j+f
      dst[start&1].append((start,((takeoff-start*t//2)<<FPT)|stop))
  for j in range(2):
    dst[j].sort(reverse=True)  
  
  for k in range(2):
    h=[]
    for j in range(k,csm+1,2):  
      while len(dst[k]) and dst[k][-1][0]==j:
        heapq.heappush(h,dst[k][-1][1])
        dst[k].pop()
      while len(h) and (h[0]&MSK)<j:
        heapq.heappop(h)
      if len(h):        
        v=h[0]>>FPT
        dp[i+1][j] = min(v+j*t//2,dp[i+1][j])

print(min(dp[N]))