1364 - Friends
Time Limit : 2 Second
Memory Limit : 256 MB
Submission: 51
Solved: 4
- Description
君生我未生，我生君已老。 君恨我生迟，我恨君生早。
君生我未生，我生君已老。 恨不生同时，日日与君好。
我生君未生，君生我已老。 我离君天涯，君隔我海角。
我生君未生，君生我已老。 化蝶去寻花，夜夜栖芳草。
—《君生我未生，我生君已老》
Don't worry about looking handsome, Or being strong and brave. Just as you love me unconditionally, I love you just the same.
Ok! Ok! There are so many beautiful and romantic poems and stories about love, but life is life, C'est La Vie. Especially in China, to marry for money or for love is a question to every after 80s girl (or may be after 90s girls soon). As an old Chinese proverb says: One cannot have fish and bear's paw at the same time. However, as we know, people are not so easy to satisfy. We want love and bread both.
Now, we have the problem. There N boys and N girls, The girls has their own standard of boy friend selection, (Li, Mi), Li is the least love rate the ith girl want, Mi is the least money the ith girl want. Every boy has a attribute, (Lj, Mj), is the love rate the jth boy can give, is the money the jth boy have. If one pair of girl and boy, whose Li ≤Lj and Mi≤Mj, we can mate the ith girl with jth boy. Every girl (boy) can match with at most one boy (girl). And we want to know how many pairs of friends can be mating at most.- Input
- The input contain multiple test cases, the first line of each case is an integer N(N≤100,000). The next N line, each line with two integer Li and Mi, indicate the rate of each girl. And the N line followed, each line with two integer Lj and Mj, indicate the rate of each boy.
- Output
- For each test case, output the max number of pairs of boy and girl can be mating.
- sample input
-
2 1 1 2 2 1 2 2 2 3 2 2 4 3 3 4 0 0 3 3 4 4
- sample output
-
2 2
- hint
- source
- 中国地质大学(武汉)第七届ACM程序设计大赛暨华中地区部属高校ACM邀请赛