Please solve in Python using dynamic programming bottom up approach.... must run in n(k) time.

Yuck Donald's is considering opening a series of restaurants along Quaint Valley Highway (QVH). Then possible locations are along a straight line, and the distances between these locations from the start of QVH are, in miles and in increasing order, m_1, m_2, ..., m_n. The constraints are as follows: At each location, Yuck Donald's may open at most one restaurant. The expected profit from opening a restaurant at location i is p_i, where p_i > 0 and i = 1, 2, ..., n. Any two restaurants should be at least k miles apart, where k is a positive integer. (The restaurants can also be at the distance of k miles from each other.) Compute the maximum total profit subject to the given constraints. Input the input will have three lines. In each line, we will have space separated numbers. The first line of the input contains n and k -- the number locations and the lower bound on the distance (in miles) between consecutive restaurants. The second line contains the n locations m_1, ..., m_n. The third line contains the vector of n profits p_1, ..., p_n. The inputs satisfy the following constraints: 0 lessthanorequalto n lessthanorequalto 20000,0