ფესტივალი

დროის ლიმიტი: 6 წმ

მეხსიერების ლიმიტი: 128 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: პოლონეთი, ოლიმპიადა 19, ეტაპი 1


 თქვენ მონაწილეობას იღებთ ბაიტბურგში გამართულ საქველმოქმედო ფესტივალში, თუმცა რამდენიმე ატრაქციონი გამოგრჩათ, მათ შორის დაბრკოლებების რბოლა. ლოგიკური გამოცანების მოყვარული ბაიტაზარი კი დიდ შემოწირულობას გპირდებათ, თუ მის გამოცანას გამოიცნობთ.

 თქვენ არ იცით რბოლის ზუსტი შედეგები, მაგრამ ბაიტაზარი გარკვეულ ინფორმაციას გაწვდით მათ შესახებ და გეკითხებათ, მაქსიმუმ რამდენი განსხვავებული შედეგი შეიძლებოდა დაფიქსირებულიყო ამ რბოლაში. ორ მონაწილეს განსხვავებული შედეგები აქვთ, თუკი მათ ფინიშის ხაზი ერთდროულად არ გადაუკვეთავთ. (ცნობილია, რომ თითოეული მონაწილის მიერ დაფიქსირებული შედეგი - წამების რაოდენობა მთელი რიცხვია.) თქვენ ასევე იცით მორბენალთა ზოგიერთი წყვილის შედეგების ურთიერთდამოკიდებულება. ბაიტაზარი გაძლევთ ზოგიერთ წყვილს (A, B),სადაც A-ს შედეგი 1წამით სჯობდა B-ს, და ზოგიერთ წყვილს (C, D), სადაც C-ს შედეგი D-ს მსგავსი ან უკეთესი შედეგი აქვს. დაწერეთ პროგრამა, რომელიც დაგეხმარებათ ბაიტმენის თავსატეხის გადაჭრაში.

 

შემომავალი მონაცემები:

პირველი ხაზი: 3 სფეისით დაშორებული არაუარყოფითი რიცხვი: n, m1, m2 (2 <= n <= 600, 1 <= m1 + m2  <= 100 000), სადაც m1 არის ჩვენთვის ცნობილი პირველი ტიპის წყვილების(A,B) რაოდენობა და m2 - მეორე ტიპის (C,D). მორბენლები არიან გადანომრილი 1-იდან n-მდე.

შემდეგი m1 ხაზი: პირველი ტიპის მორბენალთა წყვილები. თითო წყვილი i სტრიქონში მოიცავს 2 სფეისით დაშორებულ რიცხვს ai და bi, სადაც ai მორბენლის შედეგი 1 წამით სჯობდა bi მორბენლისას.

შემდეგი m2 ხაზი: მეორე ტიპის მორბენალთა წყვილები. თითო წყვილი i სტრიქონში მოიცავს 2 სფეისით დაშორებულ რიცხვს ci და di, სადაც ci მორბენლის შედეგი di მორბენლისაზე უარესი არ არის.

 

გამოსატანი მონაცემები:

ერთადერთი ხაზი, რომელზეც წერია ერთი რიცხვი: მოცემული მონაცემების მიხედვით, მორბენლების მიერ დაფიქსირებული განსხვავებული შედეგების მაქსიმალური რაოდენობა.

თუ ბაიტაზარის მოცემული შეზღუდვები ვალიდურ სიტუაციას არ შეესაბამება, გამოსატანი მონაცემები უნდა შედგებოდეს ერთი ხაზისგან, რომელიც შეიცავს ერთადერთ სიტყვას „NIE” (ბრჭყალების გარეშე).

 

დამატებითი შეზღუდვა:

მინიმუმ 15%-იან ტესტებზე n <= 10.




მაგალითები

შესატანი მონაცემები
4 2 2 1 2 3 4 1 4 3 1 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება

შენიშვნა

ახსნა:

რბოლა შეიძლებოდა დამთავრებულიყო ორნაირად:

1.      მორბენალი 3 არის პირველი, მორბენლები 1 და 4 არიან მეორეები და ბოლო არის მორბენალი 2.

2.      პირველ ადგილზე არიან მორბენლები 1 და 3 და მეორე ადგილზე არიან მორბენლები 2 და 4.

ვინაიდან პირველ ვარიანტში უფრო მეტი განსხვავებული შედეგია დაფიქსირებული, პასუხი არის 3.