لدى 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