link to question is http://www.spoj.com/problems/KNAPSACK/

this is a basic 0-1 knapsack problem , which gets TLE in Python 2.7

i implemented in 1D array not a 2D array even then it gets TLE . c++ gets accepted , please dont tell me that python is slow ,time is relaxed so that shouldn’t be the reason .

code :

```
__author__ = "Achut"
s,n = map(int,raw_input().strip().split())
a = [0]*(s+1)
while n :
n = n-1
x,y = map(int,raw_input().strip().split())
if a <= 0 or y <= 0 or x > s:
continue
for i in range(s-x,0,-1):
if a[i] != 0:
a[i+x] = max(a[i]+y,a[i+x])
a[x] = max(a[x],y)
#print a
print max(a)
```