2d Knapsack

[JodsintZ]

มีตารางขนาด i * j เป็น grid
เด็กผู้ชายต้องการไปจากตำแหน่ง (1,1) ไปยัง (i,j) โดยที่ทำการเลือกม้าในการเดินทาง
โดยม้า n ตัว แต่ะละตัวมีค่าใช้จ่าย k และสามารถเดินทางได้ (x,y) ช่อง
จงหาว่าค่าใช้จ่ายน้อยที่สุดที่ทำให้เด็กผู้ชายไปถึงจุดหมายเป็นเท่าไหร่ (เดินทางเกินได้)

Sol : 2d knapsack

[jDerp]

k <= 1e9

n <= 20; expo
n <= 1000, i <= 500, j = 1; 1d knapsack
n <= 1000, i <= 500, j <= 500; 2d knapsack