8205: BZOJ4205:卡牌配对

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

现在有一种卡牌游戏,每张卡牌上有三个属性值:A,B,C。把卡牌分为X,Y两类,分别有n1,n2张。 两张卡牌能够配对,当且仅当,存在至多一项属性值使得两张卡牌该项属性值互质,且两张卡牌类别不同。 比如一张X类卡牌属性值分别是225,233,101,一张Y类卡牌属性值分别为115,466,99。那么这两张牌是可以配对的,因为只有101和99一组属性互质。 游戏的目的是最大化匹配上的卡牌组数,当然每张卡牌只能用一次。


输入格式

数据第一行两个数n1,n2,空格分割。 接下来n1行,每行3个数,依次表示每张X类卡牌的3项属性值。 接下来n2行,每行3个数,依次表示每张Y类卡牌的3项属性值。


输出格式

输出一个整数:最多能够匹配的数目。


样例输入

2 2
2 2 2
2 5 5
2 2 5
5 5 5

样例输出

2

【提示】
样例中第一张X类卡牌和第一张Y类卡牌能配对,第二张X类卡牌和两张Y类卡牌都能配对。所以最佳方案是第一张X和第一张Y配对,第二张X和第二张Y配对。
另外,请大胆使用渐进复杂度较高的算法!

提示

对于100%的数据,n1,n2≤ 30000,属性值为不超过200的正整数


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: