{"raw_statement":[{"iden":"problem statement","content":"In this world, there are $K$ types of gems numbered from $1$ to $K(=4)$. The value per unit size of a gem of type $i$ is $W_i$.\nSnuke has $N$ gems. The $i$\\-th gem is of type $A_i$ and has size $B_i$. Also, Snuke has $N$ boxes, where the $i$\\-th box has size $i$.\nSnuke will now put one gem in each box. When a gem's size is larger than the box, the gem is cut to fit in the box. That is, when gem $i$ is put in box $j$, its value becomes $W_{A_i} \\times \\min(B_i, j)$.\nFind the maximum possible sum of gem values."},{"iden":"constraints","content":"*   $K = 4$\n*   $1 \\leq W_1 < W_2 < \\cdots < W_K \\leq 10^6$\n*   $1 \\leq N \\leq 250000$\n*   $1 \\leq A_i \\leq K$\n*   $1 \\leq B_i \\leq N$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $K$\n$W_1$ $W_2$ $\\ldots$ $W_K$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_N$ $B_N$"},{"iden":"sample input 1","content":"3 4\n1 2 3 4\n4 2\n1 3\n3 2"},{"iden":"sample output 1","content":"15\n\nIf gems $1, 2, 3$ are put in boxes $3, 1, 2$, respectively, the sum of values is $4 \\times \\min(2, 3) + 1 \\times \\min(3, 1) + 3 \\times \\min(2, 2) = 15$, which is maximum."},{"iden":"sample input 2","content":"3 4\n1 2 3 4\n3 1\n2 2\n1 3"},{"iden":"sample output 2","content":"10"},{"iden":"sample input 3","content":"6 4\n1 3 8 10\n2 2\n1 4\n2 2\n3 1\n3 4\n4 3"},{"iden":"sample output 3","content":"86"},{"iden":"sample input 4","content":"15 4\n239277 249169 419371 744281\n2 14\n1 4\n1 11\n4 12\n1 7\n2 12\n3 15\n2 5\n3 4\n1 8\n3 2\n4 1\n1 15\n3 5\n2 8"},{"iden":"sample output 4","content":"39858078"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}