존은 베시에게 줄 N(1<=N<=40,000) 개의 사탕이 있다.

매일 농부 존은 베시에게 얼마나 사탕을 가지고 갈 수 있는지 선택권을 준다. 그녀가 Nopt(1<=Nopt<=50) 에 따른 C_i(1<=C_i<=N)에서 매일 사탕을 가지고 갈 수 있는 선택권을 준다. 그녀는 C_i 사탕을 많거나 적게 가지고 갈 수 없으며 정확하게 가지고 가야 한다. 농부 존은 베시를 위해 더 많은 사탕을 먹을 수 있도록 F(1<=F<=50) 에 따른 FN_i(1<=FN_i<=N)의 사탕을 남을 때마다 M(1<=M<=100)개의 사탕을 더 준다.

아래 예제 데이터를 설명하면 농부 존은 10개의 사탕을 처음에 가지고 있다. 베시는 매일 3 개 또는 5 개의 사탕을 선택해서 먹을 수 있다. 농부 존은 사탕이 2 개 또는 4 개가 남았을 때 사탕 1개를 추가할 수 있다. 다음은 베시가 선택해서 그녀가 먹어서 좋은 사탕양을 확대하기 위한 방법을 나타낸 표다.

                  처음사탕      # 먹은       남은         추가     최종
        날      #    수          사탕수     사탕수       사탕수   사탕수

         1          10             3          7            0        7
         2           7             3          4            1        5
         3           5             3          2            1        3
         4           3             3          0            0        0

입력

• 첫 번째 줄에 공백으로 분리하여 N,Nopt,F,M,을 입력받는다.
• 두번째 줄부터 Nopt 에 따른 C_i 를 입력 받는다.
• 그 다음 줄은 F에 따른 FN_i 를 입력 받는다.

출력

입출력 예

입력

10 2 2 1
3
5
4
2


출력

12

출처 : USACO 2010 NOV Silver
추천 : CONANKUN