Perica igra jednu igru na svom računaru. On ima n svojih vojnika od kojih svaki ima neku jačinu. Dato je i n protivničkih vojnika od kojih svaki takođe ima neku jačinu. Jačine tih 2n vojnika su različite (tj. ne postoje dva vojnika sa jednakim jačinama). Perica treba da uradi sledeću stvar: treba da sastavi n parova vojnika tako da se svaki par sastoji od jednog njegovog i jednog protivničkog vojnika i da se svaki od 2n vojnika pojavljuje u tačno jednom paru. I tada kreće bitka. U svakom od n dvoboja (u i-tom dvoboju (1 ≤ i ≤ n) učestvuju vojnici i-tog para) pobeđuje vojnik koji je jači. Za svakog od n protivničkih vojnika data su po dva broja: jedan koji govori koliko Perica dobija poena ukoliko njegov (Peričin) vojnik pobedi tog vojnika i drugi koji govori koliko Perica gubi poena ukoliko njegov vojnik izgubi od tog vojnika. Perica na početku ima 0 poena. Odrediti koliki je maksimalan broj poena koji Perica može skupiti (taj broj može biti i negativan).

Ulaz.

(Ulazni podaci se nalaze u datoteci vojnici.in) U prvom redu tekstualne datoteke nalazi se prirodan broj n (n ≤ 2.000). U drugom redu nalazi se n prirodnih brojeva: i-ti od tih brojeva (1 ≤ i ≤ n) predstavlja jačinu i-tog Peričinog vojnika (svaki od brojeva je manji od ili jednak 2.000.000.000). U trećem redu nalazi se n prirodnih brojeva: i-ti broj u tom redu (1 ≤ i ≤ n) predstavlja jačinu i-tog protivničkog vojnika (svaki od brojeva je manji ili jednak 2.000.000.000). U četvrtom redu nalazi se n prirodnih brojeva: i-ti broj (1 ≤ i ≤ n) predstavlja broj poena koji Perica dobija ukoliko je taj protivnički vojnik poražen (svaki od brojeva je manji od ili jednak 1.000). U petom redu nalazi se n prirodnih brojeva: i-ti broj (1 ≤ i ≤ n) predstavlja broj poena koji Perica gubi ukoliko je taj protivnički vojnik u dvoboju u kome je učestvovao izašao kao pobednik (svaki od brojeva je manji ili jednak 1.000).

Izlaz.

(Izlazne podatke upisati u datoteku vojnici.out) U prvom redu tekstualne datoteke ispisati jedan ceo broj a to je maksimalan broj poena koji Perica može skupiti.

Primer 1.

3
9 12 3
4 5 6
10 2 7
5 3 1

14

#include <stdio.h>
#include <stdlib.h>


int n;
int *A,*B,*D,*G;
int broj;

void zam(int *a,int *b)
{
  int pom=*a;
  *a=*b;
  *b=pom;
}

//prvo resenje ------------------------------------------
void sortA(int *A,int n)
{
  int br=A[n/2];
  int i=0,j=n-1;
  while (i<=j)
  {
    while (A[i]<br)
      i++;
    while (A[j]>br)
      j--;
    if (i<=j)
    {
      zam(A+i,A+j);
      i++;
      j--;
    }
  }
  if (j>0)
    sortA(A,j+1);
  if (n-i>1)
    sortA(A+i,n-i);
}

void sortB(int *B,int *D,int *G,int n)
{
  int br=B[n/2];
  int i=0,j=n-1;
  while (i<=j)
  {
    while (B[i]<br)
      i++;
    while (B[j]>br)
      j--;
    if (i<=j)
    {
      zam(B+i,B+j);
      zam(G+i,G+j);
      zam(D+i,D+j);
      i++;
      j--;
    }
  }
  if (j>0)
    sortB(B,D,G,j+1);
  if (n-i>1)
    sortB(B+i,D+i,G+i,n-i);
}


void f1()
{
  sortA(A,n);
  sortB(B,D,G,n);

  int *P1=(int *)malloc(n*sizeof(int));
  int *P2=(int *)malloc(n*sizeof(int));
  int i,j;
  for (i=0;i<n;i++)
  {
    int *pom=P2;
    P2=P1;
    P1=pom;
    if (A[i]>B[0])
      P1[0]=D[0];
    else
      P1[0]=-G[0];
    for (j=1;j<=i;j++)
    {
      P1[j]=P1[j-1]-G[j];
      if (A[i]>B[j] && P2[j-1]+D[j]>P1[j])
        P1[j]=P2[j-1]+D[j];
    }
  }
  broj=P1[n-1];
}
//-------------------------------------------------------


//drugo resenje -----------------------------------------
void sortC(int *B,int *D,int *G,int n)
{
  int br=D[n/2]+G[n/2];
  int i=0,j=n-1;
  while (i<=j)
  {
    while (D[i]+G[i]<br)
      i++;
    while (D[j]+G[j]>br)
      j--;
    if (i<=j)
    {
      zam(B+i,B+j);
      zam(G+i,G+j);
      zam(D+i,D+j);
      i++;
      j--;
    }
  }
  if (j>0)
    sortC(B,D,G,j+1);
  if (n-i>1)
    sortC(B+i,D+i,G+i,n-i);
}

void f2()
{
  sortC(B,D,G,n);
  broj=0;
  int i,j,da,k,m;
  m=n;
  for (i=n-1;i>=0;i--)
  {
    da=0;
    for (j=0;j<m;j++)
      if (A[j]>B[i])
        if (!da)
        {
          da=1;
          k=j;
        }
        else
          if (A[j]<A[k])
            k=j;
    if (da)
    {
      m--;
      zam(A+k,A+m);
      broj+=D[i];
    }
    else
      broj-=G[i];
  }
}
//-------------------------------------------------------



void main()
{
  FILE *dat=fopen("Vojnici.in","r");
  fscanf(dat,"%d",&n);
  int i;
  A=(int *)malloc(n*sizeof(int));
  B=(int *)malloc(n*sizeof(int));
  D=(int *)malloc(n*sizeof(int));
  G=(int *)malloc(n*sizeof(int));
  for (i=0;i<n;i++)
    fscanf(dat,"%d",A+i);
  for (i=0;i<n;i++)
    fscanf(dat,"%d",B+i);
  for (i=0;i<n;i++)
    fscanf(dat,"%d",D+i);
  for (i=0;i<n;i++)
    fscanf(dat,"%d",G+i);
  fclose(dat);

  f1();
  //f2();



  dat=fopen("Vojnici.out","w");
  fprintf(dat,"%d",broj);
  fclose(dat);
  
  
}