Nazrin the Greeeeeedy Mouse

题号：NC256207
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

There're $n$ cheeses in the house. The $i$ -th cheese is between point $i$ and point $i+1$ . The $i$ -th cheese's size is $a_i$ and its weight is $b_i$ .
Nazrin is at point $1$ in the beginning and wants to steal some cheeses. She has $m$ chances to take the cheeses:
In the $i$ -th time, Nazrin brings a bag of size $sz_i$ . Since she's greedy, for $i>1$ , $sz_i\ge sz_{i-1}$ always holds. She can travel from point $1$ and take some cheeses. She can only travel from point $x$ to $x+1$ , or backwards. If she wants to travel from point $x$ to point $x+1$ , she has to dig a hole on the $x$ -th cheese or take it. She can't take a cheese with a hole on it. Of course, the sum of the cheeses' size she takes in the $i$ -th time can't be larger than $sz_i$ . After taking the cheeses, she needs to go back to point $1$ .
Please maximize the sum of the weights of taken cheeses and output it.

输入描述:

The first line contains two integer  () and  ().
For the following  lines, the -th line contains two integers  () and  ().
The next line contains  integers, the -th one is  (). Notice that for , .

输出描述:

One integer, the maximum sum of the weights of taken cheeses.

示例1

输入

复制

输出

复制

备注:

In the example, Nazrin can take actions below to maximize the weight of taken cheeses:

In the first time, Nazrin stays at point  and gives up the first chance to take cheese.

In the second time, Nazrin takes the cheese between point  and point  and returns to point .

In the third time, Nazrin takes all cheeses between point  and point , and goes back to point .