Card Placement

Time limit2sMemory limit128 MB

Summary

Assign N cards with numbers and letters to N ordered bins under a numeric constraint to build the lexicographically smallest string, or report impossibility.

Level: Medium6 of 10
Topics: Greedy, Sorting, Array, String
Solved: No attempts yet

Problem

There are N cards and N bins. Each card has a positive integer and one uppercase English letter written on it. Each bin also has a positive integer written on it.

A card with number x may be placed into a bin with number b only when b <= x. Every card must be used exactly once, and every bin must receive exactly one card.

After the cards are placed, read the letters of the cards from the first bin to the last bin to form a string. Find the lexicographically smallest string that can be made under the rule. If no valid placement exists, output -1.

Input

The first line contains the number of cards N (1 <= N <= 50).

Each of the next N lines contains one card description: a positive integer x and one uppercase English letter, separated by a space. The integer on a card is at most 1000.

The last line contains N positive integers, separated by spaces. These are the numbers written on the bins in order, and each is at most 1000.

Output

Print the lexicographically smallest string that can be formed. If the cards cannot be placed according to the rule, print -1.

Examples3

Example 1
Input
```
3
1 A
2 B
3 C
2 2 1
```
Expected output
```
BCA
```
Example 2
Input
```
5
1 B
2 B
3 B
4 A
5 A
1 1 1 1 5
```
Expected output
```
ABBBA
```
Example 3
Input
```
2
1 A
1 A
2 2
```
Expected output
```
-1
```