{"problem":{"name":"Integer Cards","description":{"content":"You have $N$ cards. On the $i$\\-th card, an integer $A_i$ is written. For each $j = 1, 2, ..., M$ in this order, you will perform the following operation once: Operation: Choose at most $B_j$ cards (p","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc127_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   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$\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc127_d","tags":[],"sample_group":[["3 2\n5 1 4\n2 3\n1 5","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."],["10 3\n1 8 5 7 100 4 52 33 13 5\n3 10\n4 30\n1 4","338"],["3 2\n100 100 100\n3 99\n3 99","300"],["11 3\n1 1 1 1 1 1 1 1 1 1 1\n3 1000000000\n4 1000000000\n3 1000000000","10000000001\n\nThe output may not fit into a $32$\\-bit integer type."]],"created_at":"2026-03-03 11:01:14"}}