using System;
using System.Collections.Generic;
using System.Text;

public class SoftwareCompanies
{
 private class NetworkFlow
 {
  public const int Infinity = int.MaxValue;
  private readonly int[,] cap;
  private readonly int[,] flow;
  private readonly int n;

  public NetworkFlow(int n)
  {
   this.n = n;
   cap = new int[n,n];
   flow = new int[n,n];
  }

  public int MaxFlow(int source, int sink)
  {
   int[] prev = new int[n];
   int res = 0;
   while (true)
   {
    bool found = Bfs(prev, source, sink);
    if (!found)
     break;
    int min = Infinity;
    for (int cur = sink; cur != source; cur = prev[cur])
     min = Math.Min(min, Residual(prev[cur], cur));
    res += min;
    for (int cur = sink; cur != source; cur = prev[cur])
    {
     flow[prev[cur], cur] += min;
     flow[cur, prev[cur]] -= min;
    }
   }
   return res;
  }

  public void AddEdge(int from, int to, int capacity)
  {
   cap[from, to] = capacity;
  }

  private bool Bfs(int[] prev, int source, int sink)
  {
   bool[] mark = new bool[prev.Length];
   for (int i = 0; i < prev.Length; i++)
   {
    prev[i] = -1;
    mark[i] = false;
   }
   Queue<int> q = new Queue<int>();
   q.Enqueue(source);
   while (q.Count > 0)
   {
    int cur = q.Dequeue();
    mark[cur] = true;
    for (int i = 0; i < n; i++)
    {
     if (i == cur || mark[i] || !CanGo(cur, i))
      continue;
     prev[i] = cur;
     mark[i] = true;
     q.Enqueue(i);
    }
   }
   return mark[sink];
  }

  private bool CanGo(int a, int b)
  {
   return cap[a, b] == Infinity || Residual(a, b) > 0;
  }

  private int Residual(int a, int b)
  {
   return cap[a, b] == Infinity ? Infinity : cap[a, b] - flow[a, b];
  }
 }

 public string[] produceData(string[] names, string[] process, int[] companyCost, int[] amount, string company1, string company2)
 {
  List<string> res = null;
  int maxFlow = 0;
  int cost = 0;
  string[][] processSplitted = new string[process.Length][];
  for (int i = 0; i < processSplitted.Length; i++)
   processSplitted[i] = process[i].Split();

  for (int mask = 0; mask < (1 << names.Length); mask++)
  {
   Dictionary<string, int> ids = new Dictionary<string, int>();
   int nextId = 0;
   int ncost = 0;
   for (int i = 0; i < names.Length; i++)
   {
    if (HasBit(mask, i))
    {
     ids[names[i]] = nextId++;
     ncost += companyCost[i];
    }
   }
   if (!ids.ContainsKey(company1) || !ids.ContainsKey(company2))
    continue;

   NetworkFlow nf = new NetworkFlow(ids.Count*2);
   for (int i = 0; i < process.Length; i++)
   {
    if (HasBit(mask, i))
    {
     int myId = ids[names[i]];
     foreach (string next in processSplitted[i])
     {
      if (ids.ContainsKey(next))
       nf.AddEdge(2*myId + 1, 2*ids[next], NetworkFlow.Infinity);
     }
     nf.AddEdge(2*myId, 2*myId + 1, amount[i]);
    }
   }

   int nflow = nf.MaxFlow(2*ids[company1], 2*ids[company2] + 1);
   CheckBetterFlow(ref res, mask, nflow, ref maxFlow, ncost, ref cost, names);
  }
  return res == null ? new string[0] : res.ToArray();
 }

 private void CheckBetterFlow(ref List<string> res, int mask, int nflow, ref int maxFlow, int ncost, ref int cost, string[] names)
 {
  if (nflow == 0)
   return;
  List<string> sln = new List<string>();
  for (int i = 0; i < names.Length; i++)
  {
   if (HasBit(mask, i))
    sln.Add(names[i]);
  }
  sln.Sort();
  if (nflow > maxFlow || nflow == maxFlow && ncost < cost || nflow == maxFlow && ncost == cost && Less(sln, res))
  {
   maxFlow = nflow;
   cost = ncost;
   res = sln;
  }
 }

 private bool Less(List<string> cand, List<string> res)
 {
  if (res == null)
   return true;
  for (int i = 0; i < Math.Min(cand.Count, res.Count); i++)
  {
   if (cand[i] != res[i])
    return cand[i].CompareTo(res[i]) < 0;
  }
  return cand.Count < res.Count;
 }

 private bool HasBit(int mask, int bit)
 {
  return (mask & (1 << bit)) != 0;
 }
}