#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>
#include <deque>
#include <map>

using namespace std;

#define MAXN 1024*1024
#define x y[cs]
#define y second
#define mp make_pair
#define pb push_back
#define sz(a) (int)(a.size())
#define all(a) a.begin(), a.end()
#define R(a) ((a)%M)

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> PI;
typedef vector<PI> VPI;
typedef vector<VPI> VVPI;
typedef vector<VVPI> VVVPI;
typedef vector<VVI> VVVI;
typedef vector<double> VD;
typedef vector<VD> VVD;
typedef vector<string> VS;

double MinCostMatching(const VVD &cost, VI &Lmate, VI &Rmate) {
  int n = int(cost.size());

  // construct dual feasible solution
  VD u(n);
  VD v(n);
  for (int i = 0; i < n; i++) {
    u[i] = cost[i][0];
    for (int j = 1; j < n; j++) u[i] = min(u[i], cost[i][j]);
  }
  for (int j = 0; j < n; j++) {
    v[j] = cost[0][j] - u[0];
    for (int i = 1; i < n; i++) v[j] = min(v[j], cost[i][j] - u[i]);
  }
  
  // construct primal solution satisfying complementary slackness
  Lmate = VI(n, -1);
  Rmate = VI(n, -1);
  int mated = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (Rmate[j] != -1) continue;
      if (fabs(cost[i][j] - u[i] - v[j]) < 1e-10) {
	Lmate[i] = j;
	Rmate[j] = i;
	mated++;
	break;
      }
    }
  }
  
  VD dist(n);
  VI dad(n);
  VI seen(n);
  
  // repeat until primal solution is feasible
  while (mated < n) {
    
    // find an unmatched left node
    int s = 0;
    while (Lmate[s] != -1) s++;
    
    // initialize Dijkstra
    fill(dad.begin(), dad.end(), -1);
    fill(seen.begin(), seen.end(), 0);
    for (int k = 0; k < n; k++) 
      dist[k] = cost[s][k] - u[s] - v[k];
    
    int j = 0;
    while (true) {
      
      // find closest
      j = -1;
      for (int k = 0; k < n; k++) {
	if (seen[k]) continue;
	if (j == -1 || dist[k] < dist[j]) j = k;
      }
      seen[j] = 1;
      
      // termination condition
      if (Rmate[j] == -1) break;
      
      // relax neighbors
      const int i = Rmate[j];
      for (int k = 0; k < n; k++) {
	if (seen[k]) continue;
	const double new_dist = dist[j] + cost[i][k] - u[i] - v[k];
	if (dist[k] > new_dist) {
	  dist[k] = new_dist;
	  dad[k] = j;
	}
      }
    }
    
    // update dual variables
    for (int k = 0; k < n; k++) {
      if (k == j || !seen[k]) continue;
      const int i = Rmate[k];
      v[k] += dist[k] - dist[j];
      u[i] -= dist[k] - dist[j];
    }
    u[s] += dist[j];
    
    // augment along path
    while (dad[j] >= 0) {
      const int d = dad[j];
      Rmate[j] = Rmate[d];
      Lmate[Rmate[j]] = j;
      j = d;
    }
    Rmate[j] = s;
    Lmate[s] = j;
    
    mated++;
  }
  
  double value = 0;
  for (int i = 0; i < n; i++)
    value += cost[i][Lmate[i]];
  
  return value;
}

int N, M, K;
map<string, double> f;
VI L, R;
VVD cost;
VS d;
double inf = 1e10;

int find ( int n )
{
	if(L[n] < N)
		L[n] = find(L[n]);
	return L[n];
}

int main ()
{
	cin >> N >> M >> K;
	
	d = VS(N);
	cost = VVD(N+M, VD(N+M,0.0));
	
	string _s;
	double _p;
	for (int i = 0; i < K; i += 1)
	{
		cin >> _s >> _p;
		f[_s] = _p;
	}
	
	for (int i = 0; i < N; i += 1)
		cin >> d[i];
	
	for (int i = 0; i < N+M; i += 1)
	{
		for (int j = 0; j < N+M; j += 1)
		{
			if (i >= N)
				cost[i][j] = 0.0;
			else if (j >= N)
				cost[i][j] = f[d[i]];
			else if ( i <= j )
				cost[i][j] = inf;
			else if ( d[i] == d[j] )
				cost[i][j] = 0.8*f[d[i]];
			else
				cost[i][j] = f[d[i]];
		}
	}
	
	cout << MinCostMatching(cost, L, R) << '\n';
	
	for (int i = 0; i < N; i += 1)
		cout << find(i)-N+1 << '\n';
	
	return 0;
}

/* HackerRank Template */

import java.io.*;
import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.fill;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.sort;

public class Solution {
	
	static long initTime;
	static final Random rnd = new Random(7777L);
	static boolean writeLog = false;
	
	public static void main(String[] args) throws IOException {
//		initTime = System.currentTimeMillis();
//		try {
//			writeLog = "true".equals(System.getProperty("LOCAL_RUN_7777"));
//		} catch (SecurityException e) {}
//		new Thread(null, new Runnable() {
//			public void run() {
//				try {
//					try {
//						if (new File("input.txt").exists())
//							System.setIn(new FileInputStream("input.txt"));
//					} catch (SecurityException e) {}
//					long prevTime = System.currentTimeMillis();
//					new Solution().run();
//					writeLog("Total time: " + (System.currentTimeMillis() - prevTime) + " ms");
//					writeLog("Memory status: " + memoryStatus());
//				} catch (IOException e) {
//					e.printStackTrace();
//				}
//			}
//		}, "1", 1L << 24).start();
		new Solution().run();
	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
		in.close();
	}
	
	/*************************************************************** 
	 * Solution: min-cost-flow on multi-list
	 **************************************************************/

	final int INF = Integer.MAX_VALUE >> 1;
	final Map<String, Integer> indexes = new HashMap<String, Integer>(120);
	final int costOffset = 10000;
	final int edgesCap = 30;
	
	void solve() throws IOException  {
		
		int n = nextInt();
		int m = nextInt();
		int k = nextInt();
		
		int[] prices = new int [k];
		int[] destionations = new int [n];
		
		for (int i = 0; i < k; i++) {
			prices[indexOf(nextToken())] = 5 * nextInt();
		}
		
		for (int i = 0; i < n; i++) {
			destionations[i] = indexOf(nextToken());
		}
		
		
		
		int S = n + n;
		int T = S + 1;
		Net net = new Net(T + 1, n + n * (n - 1) / 2 + n);
		
		for (int i = 0; i < n; i++) {
			net.addDirectedEdge(S, i, 1, 0);
		}
		
		for (int i = 0; i < n; i++) {
			boolean first = true;
			int edges = 0;
			for (int j = i + 1; j < n; j++) {
				int discount = getDiscount(prices, destionations, i, j);
				if (discount == 0) {
					if (++edges <= edgesCap) {
						net.addDirectedEdge(i, n + j, 1, costOffset);
					}
				} else if (first) {
					first = false;
					net.addDirectedEdge(i, n + j, 1, costOffset - discount);
				}
			}
		}
		
		for (int i = 0; i < n; i++) {
			net.addDirectedEdge(n + i, T, 1, 0);
		}
		
		MinCostFlowAlgorithm minCostFlowAlgorithm = new MinCostFlowAlgorithm(net, S, T);
		
		int totalCost = minCostFlowAlgorithm.run(n - m);
		
		for (int i = 0; i < n; i++) {
			totalCost += prices[destionations[i]];
		}
		
		out.println(0.2 * totalCost);
		
		int[] pathIndexes = getPathIndexes(n, net);
		
		for (int pathIndex : pathIndexes) {
			out.println(pathIndex);
		}
	}
	
	int[] getPathIndexes(int n, Net net) {
		int[] pathIndexes = new int [n];
		
		int curIndex = 1;
		
		for (int i = 0; i < n; i++) {
			if (pathIndexes[i] == 0) {
				dfs(net, n, i, curIndex++, pathIndexes);
			}
		}
		
		return pathIndexes;
	}

	void dfs(Net net, int n, int v, int pathIndex, int[] pathIndexes) {
		pathIndexes[v] = pathIndex;
		
		for (int i = net.head[v]; i != 0; i = net.next[i]) {
			NetEdge edge = net.edges[i];
			if (edge.flow == 1) {
				dfs(net, n, edge.to - n, pathIndex, pathIndexes);
			}
		}
		
	}

	int getDiscount(int[] prices, int[] destionations, int i, int j) {
		if (destionations[i] == destionations[j]) {
			return prices[destionations[i]] / 5;
		}
		return 0;
	}

	int indexOf(String key) {
		Integer index = indexes.get(key);
		if (index == null) indexes.put(key, index = indexes.size());
		return index;
	}
	
	class MinCostFlowAlgorithm {
		Net net;
		int[] dist;
		int[] used;
		int[] phi;
		NetEdge[] prev;
		int tick = 1;
		
		int S, T;
		int cost;
		int flow;
		
		MinCostFlowAlgorithm(Net net, int S, int T) {
			this.net = net;
			dist = new int [net.vNum];
			used = new int [net.vNum];
			phi = new int [net.vNum];
			prev = new NetEdge [net.vNum];
			this.S = S;
			this.T = T;
		}
		
		int run(int minFlow) {
			
			cost = flow = 0;
			
			for (;;) {
				
				int pathCost = dijkstra();
				
//				if (pathCost == INF && flow < minFlow) {
//					throw new RuntimeException("Something wrong");
//				}
				
				if (pathCost >= 0 && flow >= minFlow) {
					break;
				}
				
				updateFlow();
			}
			
			return cost - flow * costOffset;
		}
		
		int dijkstra() {
			fill(dist, INF);
			tick++;
			dist[S] = 0;
			
			for (;;) {
				int v = -1;
				for (int i = 0; i < net.vNum; i++)
					if (used[i] != tick && dist[i] != INF && (v == -1 || dist[v] > dist[i]))
						v = i;
				if (v == -1) break;
				used[v] = tick;
				for (int i = net.head[v]; i != 0; i = net.next[i]) {
					NetEdge e = net.edges[i];
					if (e.restCapacity() > 0)
						if (dist[e.to] > dist[v] + e.cost + phi[v] - phi[e.to]) {
							dist[e.to] = dist[v] + e.cost + phi[v] - phi[e.to];
							prev[e.to] = e;
						}
				}
			}
			
			return dist[T];
		}
		
		void updateFlow() {
			for (int v = T; v != S; v = prev[v].from)
				cost += prev[v].inc();
			flow++;
			for (int v = 0; v < net.vNum; v++)
				phi[v] += dist[v] != INF ? dist[v] : dist[T];
		}
		
	}
	
	class NetEdge {
		int from;
		int to;
		int capacity;
		int flow;
		int cost;
		NetEdge back;
		
		NetEdge(int from, int to, int capacity, int cost) {
			this.from = from;
			this.to = to;
			this.capacity = capacity;
			this.cost = cost;
		}
		
		int restCapacity() {
			return capacity - flow;
		}
		
		void connect(NetEdge back) {
			this.back = back;
		}
		
		int inc() {
			flow++;
			back.flow--;
			return cost;
		}
	}
	
	class Net {
		int vNum;
		int[] head;
		int[] next;
		NetEdge[] edges;
		int cnt = 1;
		
		Net(int vNum, int eNum) {
			this.vNum = vNum;
			head = new int [vNum];
			next = new int [2 * eNum + 1];
			edges = new NetEdge [2 * eNum + 1];
		}
		
		void add(int v, NetEdge e) {
			next[cnt] = head[v];
			edges[cnt] = e;
			head[v] = cnt++;
		}
		
		void addDirectedEdge(int from, int to, int capacity, int cost) {
			NetEdge forward = new NetEdge(from, to, capacity, cost);
			NetEdge back = new NetEdge(to, from, 0, -cost);
			forward.connect(back);
			back.connect(forward);
			this.add(from, forward);
			this.add(to, back);
		}
	}
	
	/*************************************************************** 
	 * Input 
	 **************************************************************/
	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");
	
	String nextToken() throws IOException {
		while (!st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}
	
	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}
	
	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}
	
	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
	
	int[] nextIntArray(int size) throws IOException {
		int[] ret = new int [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextInt();
		return ret;
	}
	
	long[] nextLongArray(int size) throws IOException {
		long[] ret = new long [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextLong();
		return ret;
	}
	
	double[] nextDoubleArray(int size) throws IOException {
		double[] ret = new double [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextDouble();
		return ret;
	}
	
	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}
	
	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null)
				return true;
			st = new StringTokenizer(s);
		}
		return false;
	}
	
	/*************************************************************** 
	 * Output 
	 **************************************************************/
	void printRepeat(String s, int count) {
		for (int i = 0; i < count; i++)
			out.print(s);
	}
	
	void printArray(int[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(long[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(double[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(double[] array, String spec) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.printf(Locale.US, spec, array[i]);
		}
		out.println();
	}
	
	void printArray(Object[] array) {
		if (array == null || array.length == 0)
			return;
		boolean blank = false;
		for (Object x : array) {
			if (blank) out.print(' '); else blank = true;
			out.print(x);
		}
		out.println();
	}
	
	@SuppressWarnings("rawtypes")
	void printCollection(Collection collection) {
		if (collection == null || collection.isEmpty())
			return;
		boolean blank = false;
		for (Object x : collection) {
			if (blank) out.print(' '); else blank = true;
			out.print(x);
		}
		out.println();
	}
	
	/*************************************************************** 
	 * Utility
	 **************************************************************/
	static String memoryStatus() {
		return (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory() >> 20) + "/" + (Runtime.getRuntime().totalMemory() >> 20) + " MB";
	}
	
	static void checkMemory() {
		System.err.println(memoryStatus());
	}
	
	static long prevTimeStamp = Long.MIN_VALUE;
	
	static void updateTimer() {
		prevTimeStamp = System.currentTimeMillis();
	}
	
	static long elapsedTime() {
		return (System.currentTimeMillis() - prevTimeStamp);
	}
	
	static void checkTimer() {
		System.err.println(elapsedTime() + " ms");
	}
	
	static void chk(boolean f) {
		if (!f) throw new RuntimeException("Assert failed");
	}
	
	static void chk(boolean f, String format, Object ... args) {
		if (!f) throw new RuntimeException(String.format(format, args));
	}
	
	static void writeLog(String format, Object ... args) {
		if (writeLog) System.err.println(String.format(Locale.US, format, args));
	}
	
	static void swap(int[] a, int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	
	static void swap(long[] a, int i, int j) {
		long tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	
	static void swap(double[] a, int i, int j) {
		double tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	
	static void shuffle(int[] a, int from, int to) {
		for (int i = from; i < to; i++)
			swap(a, i, rnd.nextInt(a.length));
	}
	
	static void shuffle(long[] a, int from, int to) {
		for (int i = from; i < to; i++)
			swap(a, i, rnd.nextInt(a.length));
	}
	
	static void shuffle(double[] a, int from, int to) {
		for (int i = from; i < to; i++)
			swap(a, i, rnd.nextInt(a.length));
	}
	
	static void shuffle(int[] a) {
		if (a == null) return;
		shuffle(a, 0, a.length);
	}
	
	static void shuffle(long[] a) {
		if (a == null) return;
		shuffle(a, 0, a.length);
	}
	
	static void shuffle(double[] a) {
		if (a == null) return;
		shuffle(a, 0, a.length);
	}
	
	static long[] getPartialSums(int[] a) {
		final long[] sums = new long [a.length + 1];
		for (int i = 0; i < a.length; i++)
			sums[i + 1] = sums[i] + a[i];
		return sums;
	}
	
	static long[] getPartialSums(long[] a) {
		final long[] sums = new long [a.length + 1];
		for (int i = 0; i < a.length; i++)
			sums[i + 1] = sums[i] + a[i];
		return sums;
	}
	
	static int[] getOrderedSet(int[] a) {
		final int[] set = Arrays.copyOf(a, a.length);
		if (a.length == 0) return set;
		shuffle(set);
		sort(set);
		int k = 1;
		int prev = set[0];
		for (int i = 1; i < a.length; i++) {
			if (prev != set[i]) {
				set[k++] = prev = set[i];
			}
		}
		return Arrays.copyOf(set, k);
	}
	
	static long[] getOrderedSet(long[] a) {
		final long[] set = Arrays.copyOf(a, a.length);
		if (a.length == 0) return set;
		shuffle(set);
		sort(set);
		int k = 1;
		long prev = set[0];
		for (int i = 1; i < a.length; i++) {
			if (prev != set[i]) {
				set[k++] = prev = set[i];
			}
		}
		return Arrays.copyOf(set, k);
	}
}

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int equal(double x,double y);
void init_labels();
void augment();
void update_labels();
void add_to_tree(int x, int prevx);
double hungarian();

#define N 510             //max number of vertices in one part
#define INF 100000000    //just infinity
#define E 0.0001
#define MAX 60000

double cost[N][N];          //cost matrix
int n, max_match;        //n workers and n jobs
double lx[N], ly[N];        //labels of X and Y parts
int xy[N];               //xy[x] - vertex that is matched with x,
int yx[N];               //yx[y] - vertex that is matched with y
int S[N], T[N];         //sets S and T in algorithm
double slack[N];            //as in the algorithm description
int slackx[N];           //slackx[y] such a vertex, that
                         // l(slackx[y]) + l(y) - w(slackx[y],y) = slack[y]
int prev[N];             //array for memorizing alternating paths
char dd[100][200],ds[200];
double price[100];
int d[500],ans[500];

int main(){
  double a=0;
  int nn,m,k,i,j,t;
  scanf("%d%d%d",&nn,&m,&k);
  for(i=0;i<k;i++)
    scanf("%s%lf",&dd[i][0],price+i);
  for(i=0;i<nn;i++){
    scanf("%s",ds);
    for(j=0;j<k;j++)
      if(strcmp(ds,&dd[j][0])==0){
        d[i]=j;
        break;
      }
  }
  n=nn+m;
  for(i=0;i<n;i++)
    for(j=0;j<n;j++){
      if(j<m || j<=i)
        cost[i][j]=0;
      else if(i<m || d[i-m]!=d[j-m])
        cost[i][j]=MAX-price[d[j-m]];
      else
        cost[i][j]=MAX-price[d[j-m]]*0.8;
    }
  a=hungarian();
  for(i=0;i<m;i++){
    if(equal(cost[i][xy[i]],0))
      continue;
    t=xy[i];
    while(1){
      ans[t-m]=i+1;
      if(equal(cost[t][xy[t]],0))
        break;
      t=xy[t];
    }
  }
  printf("%.3lf\n",MAX*(double)nn-a);
  for(i=0;i<nn;i++)
    printf("%d\n",ans[i]);
  return 0;
}
int equal(double x,double y){
  if(y-x<E && x-y<E)
    return 1;
  return 0;
}

void init_labels()
{
    int x,y;
    for(x=0;x<N;x++)
      lx[x]=ly[x]=0;
    //memset(lx, 0, sizeof(lx));
    //memset(ly, 0, sizeof(ly));
    for (x = 0; x < n; x++)
        for (y = 0; y < n; y++)
            //lx[x] = max(lx[x], cost[x][y]);
            lx[x]=(lx[x]>cost[x][y])?lx[x]:cost[x][y];
}

void augment()                         //main function of the algorithm
{
    if (max_match == n) return;        //check wether matching is already perfect
    int x, y, root;                    //just counters and root vertex
    int q[N], wr = 0, rd = 0;          //q - queue for bfs, wr,rd - write and read
                                       //pos in queue
    memset(S, 0, sizeof(S));       //init set S
    memset(T, 0, sizeof(T));       //init set T
    memset(prev, -1, sizeof(prev));    //init set prev - for the alternating tree
    for (x = 0; x < n; x++)            //finding root of the tree
        if (xy[x] == -1)
        {
            q[wr++] = root = x;
            prev[x] = -2;
            S[x] = 1;
            break;
        }

    for (y = 0; y < n; y++)            //initializing slack array
    {
        slack[y] = lx[root] + ly[y] - cost[root][y];
        slackx[y] = root;
    }
//second part of augment() function
    while (1)                                                        //main cycle
    {
        while (rd < wr)                                                 //building tree with bfs cycle
        {
            x = q[rd++];                                                //current vertex from X part
            for (y = 0; y < n; y++)                                     //iterate through all edges in equality graph
                if (equal(cost[x][y] , lx[x] + ly[y]) &&  !T[y])
                {
                    if (yx[y] == -1) break;                             //an exposed vertex in Y found, so
                                                                        //augmenting path exists!
                    T[y] = 1;                                        //else just add y to T,
                    q[wr++] = yx[y];                                    //add vertex yx[y], which is matched
                                                                        //with y, to the queue
                    add_to_tree(yx[y], x);                              //add edges (x,y) and (y,yx[y]) to the tree
                }
            if (y < n) break;                                           //augmenting path found!
        }
        if (y < n) break;                                               //augmenting path found!

        update_labels();                                                //augmenting path not found, so improve labeling
        wr = rd = 0;                
        for (y = 0; y < n; y++)        
        //in this cycle we add edges that were added to the equality graph as a
        //result of improving the labeling, we add edge (slackx[y], y) to the tree if
        //and only if !T[y] &&  slack[y] == 0, also with this edge we add another one
        //(y, yx[y]) or augment the matching, if y was exposed
            if (!T[y] &&  equal(slack[y] , 0))
            {
                if (yx[y] == -1)                                        //exposed vertex in Y found - augmenting path exists!
                {
                    x = slackx[y];
                    break;
                }
                else
                {
                    T[y] = 1;                                        //else just add y to T,
                    if (!S[yx[y]])    
                    {
                        q[wr++] = yx[y];                                //add vertex yx[y], which is matched with
                                                                        //y, to the queue
                        add_to_tree(yx[y], slackx[y]);                  //and add edges (x,y) and (y,
                                                                        //yx[y]) to the tree
                    }
                }
            }
        if (y < n) break;                                               //augmenting path found!
    }

    if (y < n)                                                          //we found augmenting path!
    {
        int cx,cy,ty;
        max_match++;                                                    //increment matching
        //in this cycle we inverse edges along augmenting path
        for (cx = x, cy = y; cx != -2; cx = prev[cx], cy = ty)
        {
            ty = xy[cx];
            yx[cy] = cx;
            xy[cx] = cy;
        }
        augment();                                                      //recall function, go to step 1 of the algorithm
    }
}//end of augment() function

void update_labels()
{
    int x, y;
    double delta = INF;             //init delta as infinity
    for (y = 0; y < n; y++)            //calculate delta using slack
        if (!T[y])
            //delta = min(delta, slack[y]);
            delta=(delta<slack[y])?delta:slack[y];
    for (x = 0; x < n; x++)            //update X labels
        if (S[x]) lx[x] -= delta;
    for (y = 0; y < n; y++)            //update Y labels
        if (T[y]) ly[y] += delta;
    for (y = 0; y < n; y++)            //update slack array
        if (!T[y])
            slack[y] -= delta;
}

void add_to_tree(int x, int prevx) 
//x - current vertex,prevx - vertex from X before x in the alternating path,
//so we add edges (prevx, xy[x]), (xy[x], x)
{
    int y;
    S[x] = 1;                    //add x to S
    prev[x] = prevx;                //we need this when augmenting
    for (y = 0; y < n; y++)    //update slacks, because we add new vertex to S
        if (lx[x] + ly[y] - cost[x][y] < slack[y])
        {
            slack[y] = lx[x] + ly[y] - cost[x][y];
            slackx[y] = x;
        }
}

double hungarian()
{
    double ret = 0;                      //weight of the optimal matching
    max_match = 0;                    //number of vertices in current matching
    memset(xy, -1, sizeof(xy));    
    memset(yx, -1, sizeof(yx));
    init_labels();                    //step 0
    augment();                        //steps 1-3
    int x;
    for (x = 0; x < n; x++)       //forming answer there
        ret += cost[x][xy[x]];
    return ret;
}