{"problem":{"name":"Four Jewels","description":{"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$. Snuke has $N$ gems. The $i$\\-th gem is of type $A_i$ and has size $B_i$.","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":15000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc073_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc073_d","tags":[],"sample_group":[["3 4\n1 2 3 4\n4 2\n1 3\n3 2","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."],["3 4\n1 2 3 4\n3 1\n2 2\n1 3","10"],["6 4\n1 3 8 10\n2 2\n1 4\n2 2\n3 1\n3 4\n4 3","86"],["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","39858078"]],"created_at":"2026-03-03 11:01:13"}}