Canadian Computing Competition: 2016 Stage 1, Junior #5, Senior #2

Since time immemorial, the citizens of Dmojistan and Pegland have been at war. Now, they have finally signed a truce. They have decided to participate in a tandem bicycle ride to celebrate the truce. There are \(N\) citizens from each country. They must be assigned to pairs so that each pair contains one person from Dmojistan and one person from Pegland.

Each citizen has a cycling speed. In a pair, the fastest person will always operate the tandem bicycle while the slower person simply enjoys the ride. In other words, if the members of a pair have speeds \(a\) and \(b\) , then the bike speed of the pair is \(\max(a,b)\) . The total speed is the sum of the \(N\) individual bike speeds .

For this problem, in each test case, you will be asked to answer one of two questions:

• Question 1: what is the minimum total speed, out of all possible assignments into pairs?
• Question 2: what is the maximum total speed, out of all possible assignments into pairs?

Input Specification

The first line will contain the type of question you are to solve, which is either \(1\) or \(2\) .

The second line will contain \(N\) \((1 \le N \le 100)\) .

The third line will contain \(N\) space-separated integers: the speeds of the citizens of Dmojistan.

The fourth line will contain \(N\) space-separated integers: the speeds of the citizens of Pegland.

Each person's speed will be an integer between \(1\) and \(1\,000\,000\) .

For 8 of the 15 available marks, questions of type \(1\) will be asked. For 7 of the 15 available marks, questions of type \(2\) will be asked.

Output Specification

Output the maximum or minimum total speed that answers the question asked.

Sample Input 1

1
3
5 1 4
6 2 4

Output for Sample Input 1

12

Explanation for Output for Sample Input 1

There is a unique optimal solution:

• Pair the citizen from Dmojistan with speed \(5\) and the citizen from Pegland with speed \(6\) .
• Pair the citizen from Dmojistan with speed \(1\) and the citizen from Pegland with speed \(2\) .
• , or u , but not y ) to the end of the word. If a word has no vowel, then the last syllable is the word itself. We say that two lines rhyme if their last syllables are the same, ignoring case.

  You are to classify the form of rhyme in each verse. The form of rhyme can be perfect, even, cross, shell , or free :

  • perfect rhyme: the four lines in the verse all rhyme
  • even rhyme: the first two lines rhyme and the last two lines rhyme
  • cross rhyme: the first and third lines rhyme, as do the second and fourth
  • shell rhyme: the first and fourth lines rhyme, as do the second and third
  • free rhyme: any form that is not perfect, even, cross, or shell.

  The first line of the input file contains an integer \(N\) , the number of verses in the poem, \(1 \le N \le 5\) . The following \(4N\) lines of the input file contain the lines of the poem. Each line contains at most \(80\) letters of the alphabet and spaces as described above.

  The output should have \(N\) lines. For each verse of the poem there should be a single line containing one of the words perfect , even , cross , shell , or free describing the form of rhyme in that verse.

  Sample Input 1

  1
  One plus one is small
  one hundred plus one is not
  you might be very tall
  but summer is not

  Output for Sample Input 1

  cross

  Sample Input 2

  2
  I say to you boo
  You say boohoo
  I cry too
  It is too much foo
  Your teacher has to mark
  and mark and mark and teach
  To do well on this contest you have to reach
  for everything with a lark

  Output for Sample Input 2

  perfect
  shell

  Sample Input 3

  2
  It seems though
  that without some dough
  creating such a bash
  is a weighty in terms of cash
  But how I see
  the problem so fair
  is to write subtle verse
  with hardly a rhyme

  Output for Sample Input 3

  even
  free