extern crate core;

use std::fmt;
use std::cmp::{max, min};
macro_rules! read_line{
    () => {{
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).ok();
        line
    }};
    (delimiter: ' ') => {
        read_line!().split_whitespace().map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (delimiter: $p:expr) => {
        read_line!().split($p).map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (' ') => {
        read_line!(delimiter: ' ')
    };
    ($delimiter:expr) => {
        read_line!(delimiter: $delimiter)
    };
    (' '; $ty:ty) => {
        read_line!().split_whitespace().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
    ($delimiter:expr; $ty:ty) => {
        read_line!($delimiter).into_iter().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
}
macro_rules! let_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
#[derive(Copy, Clone)]
struct Magic {
    mp: i32, damage: usize,
}
fn main() {
    loop {
        let_all!(n: usize);
        if n == 0 {
            return
        }
        let mut monsters: Vec<usize> = Vec::with_capacity(n);
        for i in 0 .. n {
            let_all!(hp: usize);
            monsters.push(hp);
        }
        monsters.sort();
        let_all!(m: usize);
        let mut for_all = Vec::<Magic>::new();
        let mut for_single = Vec::<Magic>::new();
        for _ in 0 .. m {
            let_all!(name: String, mp: i32, target: String, damage:usize);
            match &target[..] {
                "All" => for_all.push(Magic{mp: mp, damage: damage}),
                "Single" => for_single.push(Magic{mp: mp, damage: damage}),
                _ => unreachable!()
            }
        }
        let max_health = monsters[n - 1];
        let mut min_mp_for_all: Vec<i32> = vec![-1; max_health + 1];
        let mut min_mp_for_single: Vec<i32> = vec![-1; max_health + 1];
        min_mp_for_all[0] = 0;
        min_mp_for_single[0] = 0;
        for &a in &for_all {
            for i in 0 .. max_health {
                if min_mp_for_all[i] != -1 {
                    let j = min(i + a.damage, max_health);
                    if min_mp_for_all[j] == -1 || min_mp_for_all[j] > min_mp_for_all[i] + a.mp {
                        min_mp_for_all[j] = min_mp_for_all[i] + a.mp;
                    }
                }
            }
        }
        for &s in &for_single {
            for i in 0 .. max_health {
                if min_mp_for_single[i] != -1 {
                    let j = min(i + s.damage, max_health);
                    if min_mp_for_single[j] == -1 || min_mp_for_single[j] > min_mp_for_single[i] + s.mp {
                        min_mp_for_single[j] = min_mp_for_single[i] + s.mp;
                    }
                }
            }
        }
        let single = min_mp_for_single.len();
        if min_mp_for_single[max_health] == -1 {
            min_mp_for_single[max_health] = min_mp_for_all[max_health];
        }
        for i in 1 .. min_mp_for_single.len() {
            if min_mp_for_single[single - i - 1] == -1 || min_mp_for_single[single - i - 1] > min_mp_for_single[single - i]{
                min_mp_for_single[single - i - 1] = min_mp_for_single[single - i];
            }
        }
        let mut min_mp: i32 = std::i32::MAX;
        for i in 0 .. max_health + 1 {
            if min_mp_for_all[i] != -1 {
                let mut temp = min_mp_for_all[i];
                for j in 0..n{
                    if monsters[n - j - 1] > i {
                        temp += min_mp_for_single[monsters[n - j - 1] - i]
                    }else {
                        break
                    }
                }
                if min_mp > temp {
                    min_mp = temp;
                }
            }
        }
        println!("{}", min_mp);
    }
}



Measured memory_bytes: 5064