DNA is a nucleic acid present in the bodies of living things. Each piece of DNA contains a number of genes, some of which are beneficial and increase the DNA's total health. Each gene has a health value, and the total health of a DNA is the sum of the health values of all the beneficial genes that occur as a substring in the DNA. We represent genes and DNA as non-empty strings of lowercase English alphabetic letters, and the same gene may appear multiple times as a susbtring of a DNA.
Given the following:
- An array of beneficial gene strings, . Note that these gene sequences are not guaranteed to be distinct.
- An array of gene health values, , where each is the health value for gene .
- A set of DNA strands where the definition of each strand has three components, , , and , where string is a DNA for which genes are healthy.
Find and print the respective total healths of the unhealthiest (minimum total health) and healthiest (maximum total health) strands of DNA as two space-separated values on a single line.
Input Format
The first line contains an integer, , denoting the total number of genes.
The second line contains space-separated strings describing the respective values of (i.e., the elements of ).
The third line contains space-separated integers describing the respective values of (i.e., the elements of ).
The fourth line contains an integer, , denoting the number of strands of DNA to process.
Each of the subsequent lines describes a DNA strand in the form start end d, denoting that the healthy genes for DNA strand are and their respective correlated health values are .
Constraints
- the sum of the lengths of all genes and DNA strands
- It is guaranteed that each consists of lowercase English alphabetic letters only (i.e.,
atoz).
Output Format
Print two space-separated integers describing the respective total health of the unhealthiest and the healthiest strands of DNA.
Sample Input 0
6
a b c aa d b
1 2 3 4 5 6
3
1 5 caaab
0 4 xyz
2 4 bcdybc
Sample Output 0
0 19
Explanation 0
In the diagrams below, the ranges of beneficial genes for a specific DNA on the left are highlighed in green and individual instances of beneficial genes on the right are bolded. The total healths of the strands are:
-
The total health ofcaaabis . 
The total health ofxyzis , because it contains no beneficial genes.
The total health ofbcdybcis .
The unhealthiest DNA strand is xyz with a total health of , and the healthiest DNA strand is caaab with a total health of . Thus, we print 0 19 as our answer.