This page is still under construction.

Parts of this page are still being built. What you see may change.

Dice Game

Interview

Time limit1sMemory limit128 MB

Summary
Simulate a piece on a board of cells, applying a die roll then the cell's instruction, and report how many rolls reach the goal.
Level

Easy2 of 10

Topics
Simulation, Array
Solved
No attempts yet

Problem

Sang-geun is playing a board game by himself. The board consists of NN cells, where cell 1 is the start and cell NN is the goal. Each cell has a single instruction written on it, telling how many cells to move the piece forward or backward.

Sang-geun repeats the following until he reaches the goal. First, he rolls a die and moves the piece forward by the number rolled. Then he moves the piece once more by the instruction written on the cell where the piece stopped. However, the instruction on the cell reached by following an instruction is not followed.

Landing exactly on cell NN, or moving past cell NN, both count as reaching the goal.

Given the sequence of die rolls and the board instructions, write a program that determines how many die rolls it takes for Sang-geun to reach the goal.

Input

The first line contains NN and MM, where MM is the number of times Sang-geun rolls the die. (2≤N≤10002 \le N \le 1000, 1≤M≤10001 \le M \le 1000)

Each of the next NN lines contains one integer between −999-999 and 999999. The ii-th integer is the instruction XX written on cell ii. If X=0X = 0, the piece stays where it is; if XX is positive, it moves XX cells forward; if XX is negative, it moves ∣X∣|X| cells backward.

Each of the next MM lines contains one integer between 11 and 66. The jj-th integer is the number that came up on the jj-th die roll.

The instructions on cell 11 and cell NN are always 00. It is guaranteed that the goal can always be reached within MM die rolls, and no instruction ever moves the piece to a cell numbered less than 11.

Output

Print how many die rolls it takes for Sang-geun to reach the goal.

Examples2

  1. Example 1

    Input
    10 5
    0
    0
    5
    6
    -3
    8
    1
    8
    -4
    0
    1
    3
    5
    1
    5
    
    Expected output
    5
    
  2. Example 2

    Input
    10 10
    0
    -1
    -1
    4
    4
    -5
    0
    1
    -6
    0
    1
    5
    2
    4
    6
    5
    5
    4
    1
    6
    
    Expected output
    6