There are a lot of tips telling us that some fruits must not be eaten with some other fruits, or we might get ourselves in serious trouble. For example, bananas can not be eaten with cantaloupe (哈密瓜), otherwise it will lead to kidney deficiency (肾虚).

Now you are given a long list of such tips, and a big basket of fruits. You are supposed to pick up those fruits so that it is safe to eat any of them.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers: N, the number of tips, and M, the number of fruits in the basket. both numbers are no more than 100.

Then two blocks follow. The first block contains N pairs of fruits which must not be eaten together, each pair occupies a line and there is no duplicated tips; and the second one contains M fruits together with their prices, again each pair in a line. To make it simple, each fruit is represented by a 3-digit ID number. A price is a positive integer which is no more than 1000. All the numbers in a line are separated by spaces.

Output Specification:

For each case, first print in a line the maximum number of safe fruits. Then in the next line list all the safe fruits, in increasing order of their ID's. The ID's must be separated by exactly one space, and there must be no extra space at the end of the line. Finally in the third line print the total price of the above fruits. Since there may be many different solutions, you are supposed to output the one with a maximum number of safe fruits. In case there is a tie, output the one with the lowest total price. It is guaranteed that such a solution is unique.

Sample Input:

16 20
001 002
003 004
004 005
005 006
006 007
007 008
008 003
009 010
009 011
009 012
009 013
010 014
011 015
012 016
012 017
013 018
020 99
019 99
018 4
017 2
016 3
015 6
014 5
013 1
012 1
011 1
010 1
009 10
008 1
007 2
006 5
005 3
004 4
003 6
002 1
001 2

Sample Output:

12
002 004 006 008 009 014 015 016 017 018 019 020
239

Code：

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

/**
 * 题目大意:
 * 给定 N 对禁忌水果组合（按 ID），和一个包含 M 个水果的篮子（每个水果有 ID 和价格）。
 * 要求选出一个最大的安全水果集合，使得集合中任意两个水果的 ID 不在禁忌对中。
 * 如果有多个最大集合，选择总价格最小的那个。
 * 输出：水果数量、按 ID 升序排列的水果 ID（%03d 格式）、总价格。
 * 
 * 解题思路:
 * 1. 将每个不同的水果 ID 映射到一个唯一编号（1-based），避免重复处理。
 * 2. 构建邻接矩阵 G，G[i][j] = false 表示编号 i 和 j 的水果可以共存，true 表示禁忌（不能共存）。
 *    （注意：这里用 false 表示可共存，与常见图定义相反，便于剪枝）
 * 3. 使用 DFS 回溯 + 剪枝 搜索最大独立集：
 *    - 按编号从大到小枚举起点，保证搜索顺序。
 *    - 剪枝1：如果当前路径长度 + 后续最大可能长度 <= 当前最优，剪枝。
 *    - 剪枝2：如果长度相同但价格已不优，剪枝。
 *    - 检查新节点是否与路径中所有节点可共存。
 * 4. 使用数组 cnt[] 记录从每个编号开始能选的最大数量，用于剪枝。
 * 5. 输出时还原原始 ID，排序并格式化。
 */
public class Main {

    // 全局变量
    private static int fruitCount;               // 水果种类数（去重后）
    private static int[] price;                  // price[i] = 编号为 i 的水果的价格
    private static boolean[][] conflict;         // conflict[i][j] = true 表示 i 和 j 不能共存
    private static int[] maxFrom;                // maxFrom[i] = 从编号 i 开始能选的最大水果数（剪枝用）
    
    private static int bestSize = 0;             // 当前找到的最大安全集合大小
    private static int bestCost = Integer.MAX_VALUE; // 当前最小总价格
    
    private static int[] currentPath;            // DFS 当前路径（存储编号）
    private static int[] optimalPath;            // 最优解路径

    /**
     * 深度优先搜索，寻找最大独立集
     * @param start 当前选择的起始编号
     * @param currentSize 当前路径中的水果数量
     * @param currentCost 当前路径的总价格
     */
    private static void dfs(int start, int currentSize, int currentCost) {
        // 剪枝：即使后面全选也无法超越当前最优解
        for (int next = start + 1; next <= fruitCount; next++) {
            if (maxFrom[next] + currentSize < bestSize) return;
            if (maxFrom[next] + currentSize == bestSize && currentCost >= bestCost) return;
            
            // 只有不冲突的水果才可尝试加入
            if (!conflict[start][next]) {
                boolean canAdd = true;
                // 检查 next 是否与当前路径中所有水果都可共存
                for (int i = 0; i < currentSize; i++) {
                    if (conflict[next][currentPath[i]]) {
                        canAdd = false;
                        break;
                    }
                }
                if (canAdd) {
                    currentPath[currentSize] = next;
                    dfs(next, currentSize + 1, currentCost + price[next]);
                }
            }
        }
        
        // 更新最优解
        if (currentSize > bestSize || (currentSize == bestSize && currentCost < bestCost)) {
            bestSize = currentSize;
            bestCost = currentCost;
            System.arraycopy(currentPath, 0, optimalPath, 0, currentSize);
        }
    }

    /**
     * 求解最大安全水果集合（最大独立集）
     * 采用从后往前的顺序，利用 maxFrom 数组剪枝
     */
    private static void solveMaxIndependentSet() {
        bestSize = 0;
        bestCost = Integer.MAX_VALUE;
        Arrays.fill(maxFrom, 0);
        
        // 从最后一个编号开始向前搜索
        for (int i = fruitCount; i >= 1; i--) {
            currentPath[0] = i;
            dfs(i, 1, price[i]);
            maxFrom[i] = bestSize; // 记录从 i 开始能选的最大数量
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split("\\s+");
        int forbiddenPairs = Integer.parseInt(firstLine[0]); // 禁忌对数量
        int totalFruits = Integer.parseInt(firstLine[1]);    // 篮子中水果总数

        // 初始化数据结构
        price = new int[105];
        conflict = new boolean[105][105];
        maxFrom = new int[105];
        currentPath = new int[105];
        optimalPath = new int[105];

        // 默认所有水果之间可以共存（无冲突）
        for (int i = 1; i <= 100; i++) {
            Arrays.fill(conflict[i], false);
        }

        // 存储禁忌对
        List<int[]> bans = new ArrayList<>();
        for (int i = 0; i < forbiddenPairs; i++) {
            String[] pair = br.readLine().split("\\s+");
            int id1 = Integer.parseInt(pair[0]);
            int id2 = Integer.parseInt(pair[1]);
            bans.add(new int[]{id1, id2});
        }

        // 映射：水果ID -> 内部编号，避免重复
        Map<Integer, Integer> idToIndex = new HashMap<>();
        Map<Integer, Integer> indexToId = new HashMap<>();
        fruitCount = 0;

        // 读取篮子中的水果
        for (int i = 0; i < totalFruits; i++) {
            String[] item = br.readLine().split("\\s+");
            int fruitId = Integer.parseInt(item[0]);
            int cost = Integer.parseInt(item[1]);

            // 如果该 ID 尚未分配编号，则分配新编号
            if (!idToIndex.containsKey(fruitId)) {
                fruitCount++;
                idToIndex.put(fruitId, fruitCount);
                indexToId.put(fruitCount, fruitId);
            }

            // 更新该编号对应水果的价格（每个 ID 只出现一次）
            price[fruitCount] = cost;
        }

        // 建立冲突关系
        for (int[] ban : bans) {
            int id1 = ban[0], id2 = ban[1];
            if (idToIndex.containsKey(id1) && idToIndex.containsKey(id2)) {
                int idx1 = idToIndex.get(id1);
                int idx2 = idToIndex.get(id2);
                conflict[idx1][idx2] = true;
                conflict[idx2][idx1] = true;
            }
        }

        // 求解最大独立集
        solveMaxIndependentSet();

        // 收集最优解对应的原始水果 ID
        List<Integer> selectedIds = new ArrayList<>();
        for (int i = 0; i < bestSize; i++) {
            int internalIndex = optimalPath[i];
            selectedIds.add(indexToId.get(internalIndex));
        }
        Collections.sort(selectedIds);

        // 输出结果
        System.out.println(bestSize);
        if (bestSize > 0) {
            System.out.printf("%03d", selectedIds.get(0));
            for (int i = 1; i < selectedIds.size(); i++) {
                System.out.printf(" %03d", selectedIds.get(i));
            }
        }
        System.out.println();
        System.out.println(bestCost);

        br.close();
    }
}