Polycarp is playing a game called "Running Over The Bridges". In this game he has to run over n bridges from the left to the right. Bridges are arranged one after the other, so the i -th bridge begins where the ( i - 1) -th bridge ends. You have the following data about bridges: l i and t i — the length of the i -th bridge and the maximum allowed time which Polycarp can spend running over the i -th bridge. Thus, if Polycarp is in the beginning of the bridge i at the time T then he has to leave it at the time T + t i or earlier. It is allowed to reach the right end of a bridge exactly at the time T + t i . Polycarp can run from the left side to the right one with speed 0.5 , so he will run over a bridge with length s in time 2· s . Besides, he has several magical drinks. If he uses one drink, his speed increases twice (i.e. to value 1) for r seconds. All magical drinks are identical. Please note that Polycarp can use a drink only at integer moments of time, and he drinks it instantly and completely. Additionally, if Polycarp uses a drink at the moment T he can use the next drink not earlier than at the moment T + r . What is the minimal number of drinks Polycarp has to use to run over all n bridges? If this number is not greater than 10 5 , then you have to find out the moments of time when Polycarp has to use each magical drink. The first line contains two integers n and r ( 1 ≤ n ≤ 2·10 5 , 1 ≤ r ≤ 10 12 ) — the number of bridges and the duration of the effect of a magical drink. The second line contains a sequence of integers l 1 , l 2 , ..., l n ( 1 ≤ l i ≤ 5·10 6 ), where l i is equal to the length of the i -th bridge. The third line contains a sequence of integers t 1 , t 2 , ..., t n ( 1 ≤ t i ≤ 10 7 ), where t i is equal to the maximum allowed time which Polycarp can spend running over the i -th bridge. The first line of the output should contain k — the minimal number of drinks which Polycarp has to use, or -1 if there is no solution. If the soluti