Gangsters#850
gangsters gather at a restaurant. The -th gangster arrives at time T_i with wealth P_i. The restaurant door has K + 1 degrees of openness, denoted by integers in the range . Each unit of time, the door's degree of openness can change by at most one: it may open by one, close by one, or remain the same. At the initial moment, the door is closed (degree ).
The -th gangster enters if, at his arrival time, the door's openness matches his required stoutness S_i. Otherwise, he leaves and does not return.
The restaurant operates during the time interval .
The goal is to gather gangsters with the maximal total wealth by operating the door appropriately.
The first line contains , , . The second line contains T_1, T_2, \ldots, T_N. The third line contains P_1, P_2, \ldots, P_N. The fourth line contains S_1, S_2, \ldots, S_N. Numbers in each line are separated by spaces.
1 \leq N \leq 100; 1 \leq K \leq 100; 1 \leq T \leq 30000; 0 \leq T_i \leq T; 1 \leq P_i \leq 300; 1 \leq S_i \leq K; all numbers are integers.
Output a single integer — the maximal total wealth of the gangsters who enter the restaurant. If no one can enter, output .
Example 1