title: Dynamic Programming: Find possible ways to reach destination
body: <p>I'm trying to solve this problem, O(N^2) solution is simple, O(N) is possible, but I cannot think of how. Here's the question:</p>
  
  <hr>
  
  <p>There are N cities and N directed roads in Steven's world. The cities are numbered from 0 to N - 1. Steven can travel from city i to city (i + 1) % N, ( 0-> 1 -> 2 -> .... -> N - 1 -> 0).</p>
  
  <p>Steven wants to travel around the world by car. The capacity of his car's fuel tank is C gallons. There are a[i] gallons he can use at the beginning of city i and the car takes b[i] gallons to travel from city i to (i + 1) % N.</p>
  
  <p>How many cities can Steven start his car from so that he can travel around the world and reach the same city he started?</p>
  
  <p>Note</p>
  
  <p>The fuel tank is initially empty.</p>
  
  <p>Input Format 
  The first line contains two integers (separated by a space): city number N and capacity C.
  The second line contains N space-separated integers: a[0], a[1], … , a[N - 1]. 
  The third line contains N space-separated integers: b[0], b[1], … , b[N - 1].</p>
  
  <p>Output Format 
  The number of cities which can be chosen as the start city.</p>
  
  <p>Sample Input</p>
  
  <p>3 3<br>
  3 1 2<br>
  2 2 2<br>
  Sample Output</p>
  
  <p>2<br>
  Explanation</p>
  
  <p>Steven starts from city 0, fills his car with 3 gallons of fuel, and use 2 gallons of fuel to travel to city 1. His fuel tank now has 1 gallon of fuel. 
  On refueling 1 gallon of fuel at city 1, he then travels to city 2 by using 2 gallons of fuel. His fuel tank is now empty. 
  On refueling 2 gallon of fuel at city 2, he then travels back to city 0 by using 2 gallons of fuel.</p>
  
  <p>Here is the second possible solution. 
  Steven starts from city 2, fill his car with 2 gallons, and travels to city 0. 
  On refueling 3 gallons of fuel from city 0, he then travels to city 1, and exhausts 2 gallons of fuel. His fuel tank contains 1 gallon of fuel now. He can then refuel 1 gallon of fuel at City 1, and increase his car's fuel to 2 gallons and travel to city 2.</p>
  
  <p>However, Steven cannot start from city 1, because he is given only 1 gallon of fuel, but travelling to city 2 requires 2 gallons.</p>
  
  <p>Hence the answer 2.</p>
  
  <hr>
  
  <p>Now I know this algorithm could be solved in O(N) time complexity, which I am unable to,  guess it can be solved using dynamic programming, please help me get a clue how it could be broken into sub problems.</p>