import java.util.* ;
import java.io.*; 
 
public class Solution {

	public static int highwayBillboard(int[] billboards, int[] revenue, int m, int x) {
	 	//making a HM to store billboards and their revenue
		 HashMap<Integer,Integer> map = new HashMap<>();

		 for(int i = 0 ; i < billboards.length ; i++)
		 map.put(billboards[i],revenue[i]);

		 //making dp 
		 int dp[] = new int[m+1];	//+1 for 0th mile
		 dp[0] = 0;
		 
		 for(int i =1 ; i <= m ; i++){

			 //if there exists a billboard on ith mile
			 if(map.containsKey(i)){
				 int boardNotInstalled = dp[i-1];
				 int boardInstalled = map.get(i);

				//we add dp[i- x-1] only when ith mile is greater than x+1
					if(i >= x+1)
					boardInstalled += dp[i- x-1];
				 dp[i] = Math.max(boardInstalled,boardNotInstalled);
			 }
			 else
			 dp[i] = dp[i-1];
		 }

		 return dp[m];
	}

}