VOCAL ANDROID

Time Limit : 1 sec, Memory Limit : 65536 KB

B: VOCAL ANDROID

ボーカルアンドロイド (VOCAL ANDROID) とは,メロディと歌詞を入力して音声を合成する作曲ツールである. 2013年3月9日に和歌山県で開催された,ボーカルアンドロイドのライブに行ったあなたは,音楽の素晴らしさに感動した. そこで,あなたは新作ボーカルアンドロイド「立音リプロ (CV.立命太郎)」を購入し,作曲を始めることにした. ところが,メロディは完成したものの作詞で詰まってしまった.

使いたいフレーズはいくつか断片的に用意しており,それらを組み合わせて各メロディにあてはめる. 各メロディは,長さが決まっており,必ずこの長さぴったりになるようにフレーズをあてはめる必要がある. また,各フレーズには,そのフレーズを使うと得られるノリの良さを表す得点と,下限の長さと上限の長さが決まっている. フレーズは,長さが整数であれば,下限から上限まで自由に調整できる. ただし,長さを変更しても,得られる点数は変わらない. 図1は,サンプルの1番目の例である.

メロディに対するフレーズの割り当て

図1: メロディに対するフレーズの割り当て

あなたの仕事はメロディの長さぴったりにフレーズを組み合わせて,できるだけ得点の総和が高い曲を作ることである. 同じフレーズは何度も使用してよいものとする.

Input

入力は以下の形式で与えられる.

n
s1 l1 p1

sn ln pn
m
w1

wm

1行目には n ( 1 ≦ n ≦ 393 ) が与えられ, その後 n 行には歌詞に使うフレーズの情報が与えられる. si, li ( 1 ≦ si < li ≦ 393 ) は, そのフレーズの長さの下限と上限であり, pi ( 1 ≦ pi ≦ 393 ) は,そのフレーズの得点を表す.

m ( 1 ≦ m ≦ 393 ) は,メロディの数を表し, その後 m 行にメロディの長さ wi ( 1 ≦ wi ≦ 393 ) が与えられる.

Output

以下のような形式で各メロディの得点を出力せよ.

1 行目 メロディ 1 の最大得点

m 行目 メロディ m の最大得点

ただし,1つでもフレーズをぴったり当てはめられないメロディが存在する場合には,-1のみを出力せよ.

Sample Input 1

3
4 5 15
2 3 4
7 8 39
2
6
8

Sample Output 1

19
39

Sample Input 2

1
2 3 10
2
3
1

Sample Output 2

-1

Source: Ritsumeikan University Competitive Programming Camp 2013, Day3 , Problem set from Ritsumeikan University teams, Shiga, Japan, 2013-03-13
Problem Setter:  yeast04 ,  lefb766, bu_u_ta_n