{"raw_statement":[{"iden":"problem statement","content":"You have $N$ cards. On the $i$\\-th card, an integer $A_i$ is written.\nFor each $j = 1, 2, ..., M$ in this order, you will perform the following operation once:\nOperation: Choose at most $B_j$ cards (possibly zero). Replace the integer written on each chosen card with $C_j$.\nFind the maximum possible sum of the integers written on the $N$ cards after the $M$ operations."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq M \\leq 10^5$\n*   $1 \\leq A_i, C_i \\leq 10^9$\n*   $1 \\leq B_i \\leq N$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $...$ $A_N$\n$B_1$ $C_1$\n$B_2$ $C_2$\n$\\vdots$\n$B_M$ $C_M$"},{"iden":"sample input 1","content":"3 2\n5 1 4\n2 3\n1 5"},{"iden":"sample output 1","content":"14\n\nBy replacing the integer on the second card with $5$, the sum of the integers written on the three cards becomes $5 + 5 + 4 = 14$, which is the maximum result."},{"iden":"sample input 2","content":"10 3\n1 8 5 7 100 4 52 33 13 5\n3 10\n4 30\n1 4"},{"iden":"sample output 2","content":"338"},{"iden":"sample input 3","content":"3 2\n100 100 100\n3 99\n3 99"},{"iden":"sample output 3","content":"300"},{"iden":"sample input 4","content":"11 3\n1 1 1 1 1 1 1 1 1 1 1\n3 1000000000\n4 1000000000\n3 1000000000"},{"iden":"sample output 4","content":"10000000001\n\nThe output may not fit into a $32$\\-bit integer type."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}