水果安全

题目描述

有些水果不能一起吃， 否则会出问题。 例如香蕉和哈密瓜不能一起吃， 否则会引起肾虚。现给定一长串不能一起吃的水果禁忌清单， 还有一大篮子水果， 你的任务是从篮子里挑出能随便组合且安全食用的水果。

时间限制： 14000        内存限制： 262144

输入

输入在第一行中给出两个正整数： N 为禁忌数量， M 为篮子里的水果数量， 均不超过 100。 最后给出两大块信息。

第一块包含 N 行， 每行给出一对不能一起吃的水果。 题目保证每一对都不同。 

第二块包含 M 行， 每行给出一种水果的编号和价格。 

水果编号是一个 3 位数字， 价格是不超过 1000 的正整数。 一行中的数字间以空格分隔。

输出

首先在一行中输出可以安全食用的水果的最大数量。 在下一行输出所有这些安全的水果，按编号升序。 编号间必须以一个空格分隔， 行首尾不得有多余空格。 最后第三行输出这些水果的总价。 解有可能不唯一， 你需要输出数量最大的解； 如果有并列， 则输出总价最低的解。 题目 保证这样的解是唯一的。

样例输入

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

样例输出

12

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

239