// Created by Kaidul Islam on 7/02/2017. // Copyright © 2017 Kaidul Islam. All rights reserved. // // #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i, n) for(__typeof(n) i = 0; i < (n); i++) #define rrep(i, n) for(__typeof(n) i = (n) - 1; i >= 0; --i) #define rep1(i, n) for(__typeof(n) i = 1; i <= (n); i++) #define FOR(i, a, b) for(__typeof(b) i = (a); i <= (b); i++) #define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i) #define SIZE(v) ((int)v.size()) #define INF (1 << 30) #define PI acos(-1.0) #define bitcnt __builtin_popcount #define pb push_back #define ppb pop_back #define all(x) x.begin(), x.end() #define mem(x, y) memset(x, y, sizeof x) #define eps 1e-9 #define pii pair #define couple make_pair #define X first #define Y second #define vi vector #define vpii vector< pii > #define si set #define SDi(x) sf("%d", &x) #define SD2(x, y) sf("%d %d", &x, &y) #define SD3(x, y, z) sf("%d %d %d", &x, &y, &z) #define SDs(x) sf("%s", x) #define pf printf #define print(x) pf("%d ", x) #define println(x) pf("%d\n", x) #define output(x, y); pf("Case %d: %d", ++x, y) #define newLine pf("\n") #define sf scanf #define READ(f) freopen(f, "r", stdin) #define WRITE(f) freopen(f, "w", stdout) #if ( _WIN32 or __WIN32__ ) #define LLD "%I64d" #else #define LLD "%lld" #endif #define SDl(x) sf(LLD, &x) #define MAX5 100001 #define MAX7 10000001 #define MAX9 1000000000 #define MOD9 (MAX9 + 7) typedef long long i64; typedef unsigned long long ui64; const i64 INF64 = (i64) 1E18; template string toStr(T n) { ostringstream oss; oss << n; oss.flush(); return oss.str(); } template T toInt(string s) { T n = 0; istringstream sin(s); sin >> n; return n; } class TimeTracker { clock_t start, end; public: TimeTracker() { start = clock(); } ~TimeTracker() { end = clock(); fprintf(stderr, "%.3lf s\n", (double)(end - start) / CLOCKS_PER_SEC); } }; struct Point { int x, y; Point(): x(0), y(0) {} Point(int a, int b): x(a), y(b) {} bool operator < (const Point& other) const { return x < other.x; } }; // BitMask int Set(int N, int pos) { return N |= (1 << pos); } int Reset(int N, int pos) { return N &= ~(1 << pos); } int Check(int N, int pos) { return (N & (1 << pos)); } int toggle(int N, int pos) { return N ^= (1 << pos); } // direction array //int dx[] = {0, -1, 0, 1}; //int dy[] = {-1, 0, 1, 0}; //int Dx[] = {0, -1, -1, -1, 0, 1, 1, 1}; //int Dy[] = {-1, -1, 0, 1, 1, 1, 0, -1}; //int _row, _col; //inline bool isValid(int i, int j) { // return i >= 0 and j >= 0 and i < _row and j < _col; //} #define MOD (MAX9 + 7) inline void IncMod(int &x, int y) { x += y; if (x >= MOD) { x -= MOD; } } #define keyType int class Compare { public: bool operator() (keyType& lhs, keyType& rhs) const { return lhs > rhs; } } compare; // e.g. sort(all(arr), compare) #define error(args...) { vector _v; split(#args, ',', _v); err(_v.begin(), args); } void split(const string& s, char c, vector& result) { stringstream ss(s); string x; while (getline(ss, x, c)) result.push_back(x); } void err(vector::iterator it) {} template void err(vector::iterator it, T a, Args... args) { cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n'; err(++it, args...); } /* error(a, b, c) output: a = 4 b = 8 c = 9 */ /** Implementation **/ #define MAX (MAX5 + 1) string g[MAX]; int h[MAX]; const static int SIZE = 30; class trie { private: struct trieNode { vector health; trieNode* children[SIZE]; trieNode(): health(vector()) { for(int i = 0; i < SIZE; ++i) { children[i] = nullptr; } } /* ~trieNode() { for(int i = 0; i < MAX; ++i) { delete children[i]; children[i] = nullptr; } } */ }; trieNode* root; public: trie(): root(new trieNode()) { } ~trie() { delete root; root = nullptr; } void insert(string const& key, int id) { trieNode* pCrawl = root; for(int i = 0; i < key.length(); ++i) { int indx = key[i] - 'a'; if(!pCrawl->children[indx]) { pCrawl->children[indx] = new trieNode(); } pCrawl = pCrawl->children[indx]; } pCrawl->health.push_back(id); } i64 search(int k, string const& key, int start, int end) { i64 total = 0; trieNode *pCrawl = root; for(int i = k; i < key.length(); ++i) { int indx = key[i] - 'a'; if(!pCrawl->children[indx]) { return total; } pCrawl = pCrawl->children[indx]; if(!pCrawl->health.empty()) { rep(i, SIZE(pCrawl->health)) { if(pCrawl->health[i] >= start and pCrawl->health[i] <= end) { total += h[pCrawl->health[i]]; } } } } return total; } }; int main(int argc, const char * argv[]) { int n; SDi(n); rep(i, n) { cin >> g[i]; } rep(i, n) { SDi(h[i]); } trie T; rep(i, n) { T.insert(g[i], i); } int q; SDi(q); int start, end; string d; i64 Max = LLONG_MIN, Min = LLONG_MAX; while(q--) { SD2(start, end); cin >> d; i64 h = 0; rep(i, SIZE(d)) { h += T.search(i, d, start, end); } Max = max(Max, h); Min = min(Min, h); } cout << Min << " " << Max << endl; return 0; }