競技プログラミングのエラー

前提

https://atcoder.jp/contests/abc261/tasks/abc261_d
コインを振って人生ゲームのようなものをする設定の問題で、最新の動きと今までの動きが推移すると考えて動的計画法でコードを書いてみました。するとサンプルではうまくいくのにTLEやWAが出てしまいます。

実現したいこと

正しいアルゴリズムを使っているのに出てしまうTLEの原因やWAの原因を指摘していただけるとありがたいです。

発生している問題・エラーメッセージ

WA,TLE

該当のソースコード

pypy3
1# -*- coding: utf-8 -*-
2#https://atcoder.jp/contests/abc261/tasks/abc261_d
3import sys
4input=sys.stdin.readline
5n,m=map(int,input().split())
6#深さ優先探索がおそらく有効、、？
7#わかんないけど2bit探索してみる。計算がキツかったら後で考える
8#まてまてどう考えてもおかしいN=5000だぞ
9#あ動的計画法か
10xlist=list(map(int,input().split()))
11bonus=dict(zip(range(n+1),[0 for i in range(n+1)]))#それぞれの到達ボーナスを格納
12for i in range(m):
13    c,y=map(int,input().split())
14    bonus[c]=y
15dp=[[0]+[-100 for i in range(n)]]#ij成分はi(0-n)回目のコイントス後にカウンタがjである場合のお金の最大値。どんどん追加していく。最初はコイントス前
16for i in range(1,n+1):#i(1-n)回後のコイントスの後に手に入る金額の最大値を各の場所について考える
17    dp.append([-100 for i in range(n+1)])
18    for j in range(1,i+1):#i回目でカウンタがj(1-i)となる場合
19            dp[i][j]=dp[i-1][j-1]+xlist[i-1]+bonus[j]
20    #カウンタがi回目で0となる場合
21    dp[i][0]=max(dp[i-1])
22print(dp)
23print(max(dp[n]))
24