{"problem":{"name":"Shipping Center","description":{"content":"We have $N$ pieces of baggage called Baggage $1$ through $N$, and $M$ boxes called Box $1$ through $M$. Baggage $i$ has a size of $W_i$ and a value of $V_i$. Box $i$ can contain a piece of baggage who","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc195_d"},"statements":[{"statement_type":"Markdown","content":"We have $N$ pieces of baggage called Baggage $1$ through $N$, and $M$ boxes called Box $1$ through $M$.\nBaggage $i$ has a size of $W_i$ and a value of $V_i$.\nBox $i$ can contain a piece of baggage whose size of at most $X_i$. It cannot contain two or more pieces of baggage.\nYou will be given $Q$ queries. In each query, given two integers $L$ and $R$, solve the following problem:\n\n*   Problem: Out of the $M$ boxes, $R-L+1$ boxes, Box $L,L+1,\\ldots,R$, have become unavailable. Find the maximum possible total value of a set of baggage that we can put into the remaining boxes simultaneously.\n\n## Constraints\n\n*   $1 \\leq N \\leq 50$\n*   $1 \\leq M \\leq 50$\n*   $1 \\leq Q \\leq 50$\n*   $1 \\leq W_i \\leq 10^6$\n*   $1 \\leq V_i \\leq 10^6$\n*   $1 \\leq X_i \\leq 10^6$\n*   $1 \\leq L \\leq R \\leq M$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $Q$\n$W_1$ $V_1$\n$\\vdots$\n$W_N$ $V_N$\n$X_1$ $\\ldots$ $X_M$\n$\\mathrm{Query}_1$\n$\\vdots$\n$\\mathrm{Query}_Q$\n\nEach Query is in the following format:\n\n$L$ $R$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc195_d","tags":[],"sample_group":[["3 4 3\n1 9\n5 3\n7 8\n1 8 6 9\n4 4\n1 4\n1 3","20\n0\n9\n\nIn the $1$\\-st query, only Box $4$ is unavailable. By putting Baggage $1$ into Box $1$, Baggage $3$ into Box $2$, and Baggage $2$ into Box $3$, we can put all baggage into boxes, making the total value of baggage in boxes $20$.\nIn the $2$\\-nd query, all boxes are unavailable; the answer is $0$.\nIn the $3$\\-rd query, only Box $4$ is available. By putting Baggage $1$ into Box $4$, we can make the total value of baggage in boxes $9$, which is the maximum possible result."]],"created_at":"2026-03-03 11:01:14"}}