003 - VOCAL ANDROID

時間制限 1 秒 / メモリ制限 64 MB / 得点 300 / x 0 /


TLE
1sec
MLE
64MB
得点
300

Problem

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

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

入出力例

入力例1

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

出力例1

19
39

入力例2

1
2 3 10
2
3
1

出力例2

-1