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;
    }
}