/valentine magic
#include<bits/stdc++.h>
#define ll long long
#define INF 10009876655433;
using namespace std;
// i is the index for boy and j is for girl
int dp[5005][5005];
ll a[5005];
ll b[5005];
ll n,m;
ll f(ll i,ll j)
{
//base case
if(i==n)
{
//we have paired all the boys
return 0;
}
if(j==m)
{
//we have rejected lott of girls and now no girl is available
return -1;
}
if(dp[i][j]!=-1)
{
return dp[i][j];
}
int op1=abs(a[i]-b[j])+ f(i+1,j+1);//by accepting the jth girl
int op2=f(i,j+1);//by rejecting the jth girl
return dp[i][j]=min(op1,op2);
}
int main()
{
memset(dp,-1,sizeof(dp));
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
for(int j=0;j<m;j++)
cin>>b[j];
sort(a,a+n);
sort(b,b+m);
ll ans=f(0,0);
cout<<ans<<endl;
return 0;
}
//the code is not giving correct output
suppose
input:
2 5
4 5
1 2 3 4 5
output :
-1
but output should be 0