{"raw_statement":[{"iden":"problem statement","content":"Takahashi will toss a coin $N$ times. He also has a counter, which initially shows $0$.\nDepending on the result of the $i$\\-th coin toss, the following happens:\n\n*   If it heads: Takahashi increases the counter's value by $1$ and receives $X_i$ yen (Japanese currency).\n*   If it tails: he resets the counter's value to $0$, without receiving money.\n\nAdditionally, there are $M$ kinds of streak bonuses. The $i$\\-th kind of streak bonus awards $Y_i$ yen **each time** the counter shows $C_i$.\nFind the maximum amount of money that Takahashi can receive."},{"iden":"constraints","content":"*   $1\\leq M\\leq N\\leq 5000$\n*   $1\\leq X_i\\leq 10^9$\n*   $1\\leq C_i\\leq N$\n*   $1\\leq Y_i\\leq 10^9$\n*   $C_1,C_2,\\ldots,C_M$ are all different.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$X_1$ $X_2$ $\\ldots$ $X_N$\n$C_1$ $Y_1$\n$C_2$ $Y_2$\n$\\vdots$\n$C_M$ $Y_M$"},{"iden":"sample input 1","content":"6 3\n2 7 1 8 2 8\n2 10\n3 1\n5 5"},{"iden":"sample output 1","content":"48\n\nIf he gets head, head, tail, head, head, head, in this order, the following amounts of money are awarded.\n\n*   In the $1$\\-st coin toss, the coin heads. Change the counter's value from $0$ to $1$ and receive $2$ yen.\n*   In the $2$\\-nd coin toss, the coin heads. Change the counter's value from $1$ to $2$ and receive $7$ yen. Additionally, get $10$ yen as a streak bonus.\n*   In the $3$\\-rd coin toss, the coin tails. Change the counter's value from $2$ to $0$.\n*   In the $4$\\-th coin toss, the coin heads. Change the counter's value from $0$ to $1$ and receive $8$ yen.\n*   In the $5$\\-th coin toss, the coin heads. Change the counter's value from $1$ to $2$ and receive $2$ yen. Additionally, get $10$ yen as a streak bonus.\n*   In the $6$\\-th coin toss, the coin heads. Change the counter's value from $2$ to $3$ and receive $8$ yen. Additionally, get $1$ yen as a streak bonus.\n\nIn this case, Takahashi receives $2+(7+10)+0+8+(2+10)+(8+1)=48$ yen in total, which is the maximum possible.  \nNote that streak bonuses are awarded any number of times each time the counter shows $C_i$.  \nAs a side note, if he gets head in all $6$ coin tosses, he only receives $2+(7+10)+(1+1)+8+(2+5)+8=44$ yen, which is not the maximum."},{"iden":"sample input 2","content":"3 2\n1000000000 1000000000 1000000000\n1 1000000000\n3 1000000000"},{"iden":"sample output 2","content":"5000000000\n\nNote that the answer 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}