ל-Farmer John יש $N$ ערימות של חבילות חציר ($1 \leq N \leq 5 \cdot 10^5$), והערימה ה-$i$ מכילה $a_i$ חבילות ($1 \leq a_i \leq 10^9$). הוא רוצה להסיר את כולן, ויש לו $M$ פרות ($1 \leq M \leq 2500$) הזמינות לעזור לו. אם ישכור את הפרה ה-$i$, היא תחזור על הפעולה הבאה $s_i$ פעמים ($1 \leq s_i \leq 100$) בעלות $c_i$ ($1 \leq c_i \leq 10^9$):

• אם בערימה יש לפחות $p_i$ חבילות ($1 \leq p_i \leq 10^9$), הפרה תסיר חבילה אחת.
• אם בערימה יש פחות מ-$p_i$ חבילות, הפרה לא תעשה דבר.

FJ רוצה להסיר את כל החבילות מכל ערימה. הוא יעשה זאת באמצעות שכירת פרות בזו אחר זו (אולי אותה פרה יותר מפעם אחת), עד שהערימה תתרוקן. עזרו ל-FJ למצוא את העלות המינימלית לריקון כל ערימה.

קלט

הקלט מגיע מהמסוף / stdin.

השורה הראשונה מכילה את $T$ ($1\le T\le 100$), מספר הבדיקות העצמאיות. כל בדיקה נתונה בפורמט הבא:

השורה הראשונה מכילה מספר שלם $N$. השורה השנייה מכילה $N$ מספרים שלמים, $a_1, a_2, \dots, a_N$.

השורה השלישית מכילה מספר שלם $M$. לאחר מכן, $M$ השורות הבאות מכילות את $p_i, s_i, c_i$.

מובטח שהפרות יוכלו להסיר את כל החבילות מכל ערימה. בנוסף, מובטח שסכום $N$ בכל הבדיקות אינו עולה על $5\cdot 10^5$, וסכום $M$ בכל הבדיקות אינו עולה על $2500$.

פלט

הדפיסו את הפלט למסוף / stdout.

לכל בדיקה, הדפיסו $N$ מספרים שלמים המופרדים ברווחים. המספר ה-$i$ הוא העלות להסרת כל החבילות מהערימה ה-$i$.

דוגמאות

קלט 1

2
3
15 100 10
4
101 1 1
1 4 8
9 3 5
15 2 3
3
15 100 10
4
101 1 1
1 1 5
9 1 8
15 1 3

פלט 1

29 155 21
73 328 50

הסבר

הבדיקה הראשונה: עבור הערימה האחרונה, שגודלה ההתחלתי $10$, אפשר לשכור את פרה $3$ פעם אחת בעלות $5$. היא תסיר חבילות פעמיים (ולא שלוש פעמים, כי לאחר הסרת החבילה השנייה נותרות $8$ חבילות). לאחר מכן אפשר לשכור את פרה $2$ פעמיים, ולהסיר את $8$ החבילות כך שלא תישאר אף חבילה. העלות הכוללת היא $ 5+8+8=21$.

הבדיקה השנייה: מקיימת $\max(s)=1$.

ניקוד

• קלטים 2-3: $a_i \le 100$
• קלטים 4-5: $\max(s)=1$
• קלטים 6-9: $\max(s)\le 4$
• קלטים 10-15: $\max(s)\le 20$
• קלטים 16-21: אין אילוצים נוספים.

מחבר הבעיה: Sujay Konda