dp.cs

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;

namespace workDP
{
	class MainClass
	{
		static int[,] dp;

		public static void Main (string[] args)
		{

			var maxDays = 365242;

			using (StreamReader r = new StreamReader ("/Users/osamukimura/work/tasks/tasks_365242days.txt")) {
				string line;
				line = r.ReadLine ();
				var tmp = line.Split (' ');
				//Console.WriteLine (tmp [0]);
				int count = 0;


				var days = new List<int> ();
				var wages = new List<int> ();
				while ((line = r.ReadLine ()) != null) {
					tmp = line.Split ('\t');

					//Console.WriteLine (tmp [0]);

					days.Add (Int32.Parse(tmp [0]));
					wages.Add (Int32.Parse(tmp [1]));
					count++;
				}



				dp = new int[count + 1, maxDays + 1];
				for (int i = count - 1; i >= 0; i--) {
					for (int j = 0; j <= maxDays; j++) {
						if (j < days [i]) {
							dp [i, j] = dp [i + 1, j];
						} else {
							dp [i, j] = Math.Max (
								dp [i + 1, j],
								dp [i + 1, j - days [i]] + wages [i]
							);
						}
					}
						
				}
			
				Console.WriteLine (dp[0,maxDays]);
			}
		}

	}
}