{"raw_statement":[{"iden":"statement","content":"China Mobile Shenzhen Branch was registered in $1999$. Four years later, Guangdong Collegiate Programming Contest was held for the first time. China Mobile Shenzhen Branch, along with Guangdong Collegiate Programming Contest, witnesses the prosperity and development of the computer industry in Guangdong.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/md6qj7fz.png)\n\nDuring the construction of a communication line, it is critical to carefully choose the locations for base stations. The distance from west to east of a city is $n$ kilometers. The engineers have investigated the cost to build a base station at $1, 2, \\cdots, n$ kilometers from west to east, which are $a_1, a_2, \\cdots, a_n$ respectively.\n\nTo ensure communication quality for the residents, the locations of base stations also need to meet $m$ requirements. The $i$-th requirement can be represented as a pair of integers $l_i$ and $r_i$ ($1 \\le l_i \\le r_i \\le n$), indicating that there must be at least $1$ base station between $l_i$ kilometers and $r_i$ kilometers (both inclusive) from west to east.\n\nAs the chief engineer, you need to decide the number of base stations to build and their locations, and finally calculate the minimum total cost to satisfy all requirements."},{"iden":"input","content":"There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains an integer $n$ ($1 \\le n \\le 5 \\times 10^5$) indicating the distance from west to east of the city.\n\nThe second line contains $n$ integers $a_1, a_2, \\cdots, a_n$ ($1 \\le a_i \\le 10^9$) where $a_i$ indicates the cost to build a base station at $i$ kilometers from west to east.\n\nThe third line contains an integer $m$ ($1 \\le m \\le 5 \\times 10^5$) indicating the number of requirements.\n\nFor the following $m$ lines, the $i$-th line contains two integers $l_i$ and $r_i$ ($1 \\le l_i \\le r_i \\le n$) indicating that there must be at least $1$ base station between $l_i$ kilometers and $r_i$ kilometers (both inclusive) from west to east.\n\nIt's guaranteed that neither the sum of $n$ nor the sum of $m$ of all test cases will exceed $5 \\times 10^5$."},{"iden":"output","content":"For each test case output one line containing one integer indicating the minimum total cost to satisfy all requirements."},{"iden":"note","content":"For the first sample test case the optimal solution is to build base stations at $2$ kilometers and $5$ kilometers from west to east. The total cost is $2 + 100 = 102$.\n\nFor the second sample test case the optimal solution is to build base stations at $2$ kilometers and $4$ kilometers from west to east. The total cost is $3 + 2 = 5$."}],"translated_statement":null,"sample_group":[["2\n5\n3 2 4 1 100\n3\n1 3\n2 4\n5 5\n5\n7 3 4 2 2\n3\n1 4\n2 3\n4 5","102\n5"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}