Problem Statement

When you were young and naive, you used to look up phone numbers by starting at the beginning of the phone book and flipping through the pages one at a time. By the time you found a phone number, you had usually forgotten why you wanted to call! Then you learned about binary search, and life was good. But now it has occurred to you that you might be able to do even better. You've realized that it is silly to look up a name like Wachowski by starting in the middle of the phone book. Instead, you should begin by opening the book to a page near the end.

Based on a study of the ethnicities present in your home town, you have compiled a int[] freqs of the expected relative frequencies of each letter, 'A' through 'Z'. For example, if freqs[0] is 7 and freqs[25] is 1, then you expect 7 times as many names to start with 'A' as start with 'Z'. Although it is unrealistic, you have decided to make the simplifying assumption that the same frequencies apply to the second and third letters, regardless of the values of the preceding letters. For example, among the names that start with 'F', you assume that 7 times as many have 'A' as the second letter as have 'Z' as the second letter (using the above frequencies), and among names that start with "GR", you assume that 7 times as many have 'A' as the third letter as have 'Z' as the third letter.

Each page in your phone book is labeled at the top with the three-letter prefix of the first name on that page and the three-letter prefix of the last name on that page, in the form "XXX-YYY" (nobody in your home town has a name shorter than three letters). The prefixes are always written in uppercase letters, and the pages are arranged in alphabetical order. Every page contains the same number of names, and page breaks never fall between two names that have the same three-letter prefix. You will be given information on the pages of your phone book as a String[] pages, containing the labels of all the pages in the phone book, in order.

You will be given the three-letter prefix of a name you want to look up. You intend to use the following strategy for searching the phone book. Based on your knowledge of the expected frequencies and the number of pages in the phone book, you will calculate the page where you expect the prefix to appear, and flip to that page. If it is the correct page for that prefix, you are done. Otherwise, you have narrowed down the pages on which it might appear, so you will recalculate and repeat. Eventually, you will either find the right page or discover that the prefix cannot possibly appear in the phone book (because it falls between the last name on one page and the first name on the next page, for example).

When recalculating the page where you expect the prefix to appear, you must take into account the prefixes on the pages you have seen. For example, if you have seen "HAR-JOH" on page 7 and "MCD-NAS" on page 11, and you are looking for "LOA", then you know it must appear between pages 7 and 11 (exclusive). You assume that the names on those pages, which fall between "JOH" and "MCD" (exclusive), are distributed according to the expected frequencies and calculate your next page flip accordingly.

Notice that the expected frequencies might predict that a certain prefix appears on several adjacent pages, even though we know that each prefix appears on at most a single page in the actual book. When this occurs, you will flip to the middle of those adjacent pages, rounding down if necessary. For example, if the frequencies predict that a given prefix appears on pages 22-25, you would flip to page 23.

Given freqs, pages, and the three-letter prefix of the name you are searching for, calculate the number of page flips it takes to either find the right page or discover that the prefix cannot possibly appear in the phone book. If you find the right page, return the number of page flips. If you discover that the prefix cannot appear in the phone book, return the negative of the number of page flips.

Definition

Constraints

Examples