using System;
using System.Collections.Generic;
using System.Linq;
namespace Paiza
{
    class Program
    {
        public static void Main(string[] args)
        {
            if (true)
            {
                knapsack();
            }
            else
            {
                frog11();
                knapsack();
                knapsack();
                vacation();
                frog1();
                dp1();
                abc130_b();
                abc130_c();
                abc130_b();
                arc089_a();
                abc085_c();
                abc083_b();
                abc087_b();
                ABC081A();
                ABC086A();
                ABC081B();
            }

        }

        private static void frog11()
        {
            var n = int.Parse(Console.ReadLine());
            var a = Console.ReadLine().Split(' ').Select(y => int.Parse(y)).ToArray();
            var dp = new int[n + 1];
            for (int i = 0; i < n+1; i++)
            {
                dp[i] = int.MaxValue;
            }
            dp[0] = 0;
            for (int i = 0; i < n; i++)
            {
                for (int j = 1; j <= 2; j++)
                {
                    if ( i + j <  n)
                    {
                    dp[i + j] = Math.Min(dp[i + j], dp[i] + Math.Abs(a[i] - a[i + j]));
                    }
                }
            }
            Console.WriteLine(dp[n]);
        }

        /// <summary>
        /// ナップサック問題
        /// </summary>
        private static void knapsack()
        {
            var nw = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var n = nw[0];
            var w = nw[1];

            var wv = Enumerable.Range(0, n).Select(x => Console.ReadLine().Split(' ').Select(y => long.Parse(y)).ToArray()).ToArray();

            //　n=0は無駄に終わるため。
            // w:０からwまでの値が欲しいため
            var dp = new long[n+1 , w + 1];


            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j <= w; j++)
                {
                    if (j - wv[i][0] >= 0)
                    {
                        dp[i + 1, j] = Math.Max(dp[i + 1, j], dp[i, j - wv[i][0]] + wv[i][1]);
                    }

                    dp[i + 1, j] = Math.Max(dp[i + 1, j], dp[i, j]);
                }
            }

            Console.WriteLine(dp[n,w]);
        }

        private static void vacation()
        {

            var n = int.Parse(Console.ReadLine());
            var abc = Enumerable.Range(0, n).Select(x => Console.ReadLine().Split(' ').Select(y => int.Parse(y)).ToArray()).ToArray();

            var dp = new int[n + 1, 3];

            int max = -1;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    for (int k = 0; k < 3; k++)
                    {
                        if (j == k)
                        {
                            continue;
                        }
                            dp[i + 1, k] = Math.Max(dp[i + 1, k], dp[i , j] + abc[i][k]);
                    }
                }
            }
            max = 0;
            for (int i = 0; i < 3; i++)
            {
                max = Math.Max(max, dp[n , i]);
            }

            Console.WriteLine(max);
        }

        /// <summary>
        /// 動的計画法
        /// </summary>
        private static void frog1()
        {
            var nm = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var n = nm[0];
            var m = nm[1];
            var k = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

            var dp = new int[n].Select(x => int.MaxValue / 2).ToArray();

            dp[0] = 0;
            for (int i = 0; i < n; i++)
            {
                for (int j = 1; j <= m; j++)
                {
                    if (i - j < 0)
                    {
                        continue;
                    }
                    else
                    {
                        dp[i] = Math.Min(dp[i], dp[i - j] + Math.Abs(k[i] - k[i - j]));
                    }
                }
            }

            Console.WriteLine(dp[n - 1]);
        }

        private static void dp1()
        {

            var a = new int[50 + 1];
            var dp = new int[50 + 1];

            var n = int.Parse(Console.ReadLine());

            a[0] = 2;
            a[1] = 3;
            dp[0] = a[0];
            for (int i = 2; i < n; i++)
            {
                a[i] = a[i - 2] + a[i - 1];
            }
            Console.WriteLine(a[n - 1]);
        }

        private static void abc130_c()
        {

            var WHxy = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            var W = WHxy[0];
            var H = WHxy[1];
            var x = WHxy[2];
            var y = WHxy[3];

        }

        private static void abc130_b()
        {

            var NX = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var N = NX[0];
            var X = NX[1];

            var L = Enumerable.Range(0, 1).Concat(Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray());
            //L = Enumerable.Range(0, 1).Select(x => x).Concat(L).ToArray();
            var counter = 0;

            var D = 0;
            foreach (var item in L)
            {

                D += item;

                if (D > X)
                {
                    break;
                }
                counter++;
            }

            Console.WriteLine(counter);
        }

        private static void arc089_a()
        {
            var N = int.Parse(Console.ReadLine());
            var t = Enumerable.Range(0, N).Select(x => Console.ReadLine().Split(' ').Select(y => int.Parse(y)).ToArray()).ToArray();

            int[] prev = new int[] { 0, 0, 0 };
            foreach (var item in t)
            {
                var dt = item[0] - prev[0];
                var dist = Math.Abs(item[1] - prev[1]) + Math.Abs(item[2] - prev[2]);
                var parity = item[0] % 2 == 0;
                if (dist > Math.Abs(item[0] - prev[0]))
                {
                    Console.WriteLine("No");
                    return;
                }

                if (dist % 2 != dt % 2)
                {
                    Console.WriteLine("No");
                    return;
                }

                prev = item;
            }

            Console.WriteLine("Yes");

        }

        private static void abc085_c()
        {
            var NY = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var N = NY[0];
            var Y = NY[1];
            // 10000 5000 1000
            for (int i = 0; i <= N; i++)
            {
                for (int j = 0; j <= N - j; j++)
                {
                    var k = N - i - j;
                    if (k >= 0)
                    {
                        if (i * 10000 + j * 5000 + k * 1000 == Y)
                        {
                            Console.WriteLine($"{i} {j} {k}");
                            return;
                        }
                    }
                }
            }

            Console.WriteLine("-1 -1 -1");
        }

        private static void abc083_b()
        {
            var NAB = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToList();
            var N = NAB[0];
            var A = NAB[1];
            var B = NAB[2];
            int sums = 0;

            for (int i = 1; i <= N; i++)
            {
                var sum = i.ToString()
                           .Select(x => x.ToString())
                           .Select(x => int.Parse(x))
                           .Sum(x => x);

                if (A <= sum && sum <= B)
                {
                    sums += i;
                }
            }
            Console.WriteLine(sums);
        }

        private static void abc087_b()
        {

            var ABCX = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

            var A = ABCX[0];
            var B = ABCX[1];
            var C = ABCX[2];
            var X = ABCX[3];
            var count = 0;
            for (int i = 0; i <= A; i++)
            {
                for (int j = 0; j <= B; j++)
                {
                    for (int k = 0; k <= C; k++)
                    {
                        if (i * 500 + j * 100 + k * 50 == X)
                        {
                            count++;
                        }
                    }
                }
            }

            Console.WriteLine(count);

        }

        private static void ABC081B()
        {
            var n = int.Parse(Console.ReadLine());
            var a = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            int c = 0;
            while (a.All(x => x % 2 == 0))
            {
                a = a.Select(x => x / 2).ToArray();
                c++;
            }

            Console.WriteLine(c);
        }

        private static void ABC081A()
        {
            Console.WriteLine(Console.ReadLine().Count(x => x.ToString() == "1"));
        }

        private static void ABC086A()
        {
            var a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToList();

            Console.WriteLine((a[1] * a[0]) % 2 == 0 ? "Even" : "Odd");
        }
    }
}


Measured memory_bytes: 90208