Problem:


Score : 100 points

Problem Statement

There are N items, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Item i has a weight of w_i and a value of v_i.

Taro has decided to choose some of the N items and carry them home in a knapsack.
The capacity of the knapsack is W, which means that the sum of the weights of items taken must be at most W.

Find the maximum possible sum of the values of items that Taro takes home.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq W \leq 10^9

1 \leq w_i \leq W

1 \leq v_i \leq 10^3

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible sum of the values of items that Taro takes home.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Items 1 and 3 should be taken.
Then, the sum of the weights is 3 + 5 = 8, and the sum of the values is 30 + 60 = 90.

Sample Input 2

1 1000000000
1000000000 10

Sample Output 2

10

Sample Input 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Sample Output 3

17

Items 2, 4 and 5 should be taken.
Then, the sum of the weights is 5 + 6 + 3 = 14, and the sum of the values is 6 + 6 + 5 = 17.



Sample input:
3 8
3 30
4 50
5 60


Sample output:
90

Submission status: Accepted

Solution code:
import subprocess
import gzip, base64, os
import stat

gz = b'H4sIAAqCg10C/+19C3hTVbbwSZ/h1RREpyIjASMWkdLQAi0+aCmBE0mh0oIMioeQpjSS1yQnpTioaFvHGKrMjHfGO497mbkzfl5n7sg8L3odbOVRfINPkBE7jmBCReoDKMNA/rX23ifd5ySHxzj//b//+4zSnbX22nuvtfbaa6+998k+99oc87IMBkH5ZAk3CQgZxlYRuIrhN4VTJICrEIbA33HCWCEP4FyOrkqoUqUDrGolNTK6bPiXA/8qsihckVWlSscyOiU1cGmuwH+qVOnPnYIqFQRzqhzyus9Hsft8K1VpUQ7Fl+ary2WxcgOs3ACjV1IhS1Clinw57F8DwzcwuZR0LqOby9Hjp+6Q3Ijfi2+jcPFtVaq0ndG1a8rdAuXyhAv/FLJ0MWtPTy/FjH8lVfphqtezakb5VG/jFK/HH2md0loxY8qM8pJwoGQa4amQ0c5fuESlxyLG82hmA5hf0uUaOPzt9n9/+cPr3q7+uVU+uO7AUcybxcphl3T4C5tzxg/JMgjlwgaoGvNuhH9z4N9v/1z21tD7Nkk/cf1p58O+5O4HO1yXvVm/uW3jN6o+nfKpdEeBuaW02PaWo+vIxK7Rjw2v+bexwa3r7Gv+eC79fAgMjMqAfyMrM36qITP+t0JmfGHKwtSfcTr413Iz13O3Dn5EXmb8Szr8dOrUs1SnnnwdvFsH/+2czHiPTrvlOvVU6Oj/Dzr4a3TqKdPR82qdetbq1POZDv0UHfpFOu1+T6dfcnXsqkGn3Wd06K/Q4WelDv0KHfoTOuNivE49j+v0+9M6+Gd06r9HRz8eHX1W6/C/TkdvE3Tof60jl0+Hz0U69Xysw3+lTj0HdfQj6+Bf1OHzE53xdY2OHl7Xqf9VHT5FHXn/pNPuVVDPeGGMsCXE5l2GH8Xw/eGVqvnpmlyKF2SKX8bww3IYntWzgeF/wdrtvbxK1e58pp8tY9T4BdDuSKinl9Wv2NJdORQvRFaq5r39BtruhpCa3sT0uUHTbl0urWdzSF3Pjaz+XoYvZBnzmVwrZY1cTP9VV6jrF2AeDsuNrsmTce6dIUjSal/AL4VlZ0iWJEG6uUVa7F7tCcvuUI3XGQ67w4Jkb6iVGt0hhm6orfEG/O4G5yqvm+ZlzpGCcnPI7WyU1rjXSS74JiPS1eqUmkJut+RudbmDsifgF6TlC+vD5dBs0FoqYUthORRYZ1u8oN5pd9lIdqASMjz+sDsk27022+L6QIOEGQvq5ekueV3QDYTWMqBZ62l0+4HSI9tagKBets6UJOAjsFZaBaw4vd6Aq4WWDFvLmjz+RqnJEwrLUqDJVrfA5fPR5qY3eSPhZqWKGXwVLmdYJjVARlko4pc9PhAmFAqE5lq5AgEQwu30KUy7AGt1NTtDkhxyeuQw8AtSQA2rnGGPS6G2N0gNpZKtfoZUt6C+TPIyfZHGSc2VoGWfxw+qpCyEa6yopzDhu6EBKqwcrNDjX82qzdA60S1VrlzhCYRBtrC73A6KY2IAfgYoy+l1DyI0ArPGU5yAAvlOQ5RPhZEZd9BeRo1Md3ndzpANcqZJduAJ/snEbED0aaVKLwQi2F1SyOlf7YYmld6cQXoTbFaW/AF1h2L2TK6zNfkNduCMt0dEaGRlXbEKTN0PNiC7mjm7Bd7qJbcvKK+DsRCEwRQIOVe7bcxCrdOp1LRLVkWa9PujDGhQ2dLq1lYp6A6FA36n1wPVtpQyBabYnDuN9UoYlFUrgeLWSFBjo4Kd4QwG3f5GIiRgGr11LdAVciXITrQoo5xLL4o70g/lLtB/elkwM52yWMy/1kcKz2Stc7qrBNVR72Dz+VTGkjJLKirRPxnAQKtxH4GyYES2uZiVXtwYACvF3iYGtwhU5gs0uol8C8EdQaOtzlWeFiuaX9gjudAnSuhxYGQ3BWy887KCJGx8epnQaRoH4pkhN7iEFhA30+irYYNtAd/X5WubnbK2Y9nQw45Fp+6j/hy+rXZBjyBkFaQl/rVo9ovd4YjPjZkuStYUgDpAp+jhwfE3OT1eARQlB7xCkzvQJDStdsthxHgJGVG97G71yILP7XP5giQJrhOaXN5A2C34SL8g0hdoQTePLbFJxef0+AV0+cL8mhqprKRUmO+wz6mRppVYy1Nfp5VMF2qWLaueY5esJWUUvWwZUJeXWK0qsJKH6EoR/8sWlO85sN7Hv/gfhelfgX3PSZXB79ksPwtWm1lkxUlp8hh1HsvNZ6mRo07/Lw/ma4PQmzu4XqubuG4YrkjX5ynr4SzhDMsvhX+Pfuf7ebgL0J5HcZExniHIwyMp+hwSAyjxzRtPrcnFlfGPGL1z4AdZuMPxOIOj907KwpXyHxgsT/quEeXdzuobCNA4IU+7L8Liily2TlY+Gzj8HA6/mcPP5fBbOPwsDt/L4W0cXonfEH+9KnAdxN/Arz84/Dy+fg6vingig/hqDl0UpPh8LsYi8RmHz+LwxRw+m8OXcvgcft3J4Xk9V3H4fD4u5vBGPh7k8EM4/DIOP5TXD4cfxuGbOfxwDh/k8CM4fCuHL+DtgcObOPyDHL6Qw2/i8CM5/GMcno/7N3P4Szj8Exx+NG9vHL6Gw2/l8Jdx+C4O/zUOv5vDF3H4PRz+cg6/j8Nfwdshh7+Jw8c5/Fje/jn81zn8AIe/krfnbw7ix3FoI4fn17eFHH48b/8cfgJv/xz+Kt7+ObyFt38OfzVv/xx+Im//HP4a3v45/Gze/jn8JN7+Ofy1vP1z+Mm8/XP463j75/BTePvn8CW8/XP4qbz9c/hS3v45/Hze/jm8lbd/Dj+Nt38OX8bbP4cv5+2fw0/n7Z/Dz+Dtn8PP5O2fw1fw9s/hK/l+bPvYKMZyX7nVLIgdXXJu/DaC3GHcTvOT05+HrOTVO+CvaVwVfEO4GbMSvUn4XP0MwuiSE3sI/FuE0RUnugj8JMLoghNbCPwzhNH1JjYT+IcIo8tNbCLwdxHG6S6xgcAPIYxsJ4IEvh9hdLmJlQS+C2F0tYk6AocQRhebqCLwnQija02UEngVwuhSE2YCL0cYXWmikMCLEUYXmhAIfDPC6DoT/WcRnoNwIZGfwLMQHknkJ/A0hEcR+Ql8LcKXEPkJPAHh0UR+Ao9B+FIiP4FHIXwZkZ/AQxH+GpGfwFkIFxH5Cfy3pQBfTuQn8GcIjyHyE/gIwlcQ+Qn8AcJjifwEfhfhrxP5Cfw6wlcS+Qn8IsLjiPxnEH4eYTORn8DPIDyeyE/g3yI8gchP4CcRvorIT+CfIWwh8hP4hwhfTeQn8HcRnkjkJ/BDCF9D5Cfw/QgXE/kJfBfCk4j8BA4hfC2Rn8B3IjyZyE/gVQhfR+Qn8HKEpxD5CbwY4RIiP4FvRngqkf/vpP8RLiXyE3gWwlYiP4GnITyNyE/gaxEuI/ITeALC5UR+Ao9BeDqRn8CjEJ5B5CfwUIRnEvkJnIVwBZEf4LrnciBiih+Hr8/h3tQ2BJ+Jw2iPVwP7y7Zbj9qje+8Qox+IbR/21zXYe7q66qsEsae7jiQ9/WOrhPhhKP6FaRwEhltPQtEl4pR+SMS2gQIxemht1ortW4mvAAfxxYrnMCvZaxpHtq629nP03QPZQC9Gnxe7j8wWDXvEvQMRKPwMLfw6FBaju2j5D1j5DTcuXwbGFBm5BErG7wEBV+zKnQ8ow+fb0d+IbTcW3wIE8pUpFkYvea7fB61FDyX3rEh8C4qYxgmJME2XVN9avbR6SXVDvXjfx1vBDT2HQ2UbhpVxM0gpRrfbrCfEjgNysdj5qMUMjmvbm6iJ6Ptx7D+xp8aIzgxSEhbZowe5Gg6exhp2ih1H5XlYvBiLf0iKH4t/hxS3kWJiT7tlQHGx0V9ZsE7IM6JfhKwtLKvvKhUhfDey4HaLIUrJrEcd0d9bcPuwtuOEnGNPzjMioktQiWY7zUT7EEWbInZutJQib1jbM0MJE+/HN5zOJN+fHdGfW4oA54hFCK+oaNtDJVztH/2NiM1h3gKMPdpjPVDbkZSnVZv+uLNtYEkk257chWqpwNqiSUf0RHw9tGnvmU/ahJS06YiedsSoCPbYTWKsLL6UNGATkPmhYnKB0dTuH0o1RpllWgXuUFmO2LOES7Htbohq238H3nxXuwXXBYYY1Vp7V+Qqe3KRMfJ1eyxf7GyNP40LDrHyNVNH/jDCXPz+U8kkqhToFhK6PDVddCjSnYwvBzqx81lLLzbY+XvCQPxSCwLPWuIMiZnxLWMosp8hMTP+y8sGKeNXgl8QYz+mdYGsU1HWyCQxlq1uu2Io7bGDA9hj7YSeKCD2K1p7zAZKqHBE11uCz5lTvTL7FLECaxfWfc3NnTecIaFsHGuJZu+qMZJuZ91fRDW6T4zOtZgdMTOawRNoVYP1HRvIWN9j562v2BErBcswPewglkArro3+3XpU7PyxZTd2YeevLHtwBCwU27oGnqZj+wX58qdxzu03dRujGy2/h9ESo0lffszYeUsyWtjxwr13oW63AJLw17emCT4lpnHtbLC9n+qk4ARs/JgYPRi/9HI09fexI/YRC/wkPupSkht/qJT2ye7z9ElDEqV+P37zSdonu1N98mNSpxi7XgRbA4afIHzkJMTYfKM9mvMJ1mqBWosiV4owXHLj+SdpVckTtKp9SlXJnY7KQzA8TBvLsTXW27XRjxyxn7NqvRYj9j5qudTu6YlnC+R7kdjZbOC6rvwk13XXgr2LpqfOiN0fZcffPXG+3it0xIod0FAddGFt9DNHtMHSbI/2OaK3W1aKMa+l1PTwZmSr44Dp4R/gF89JZMPe9qqh1vNa1Tj8+oLR+npttN/e1msAJQ/2D464obUdXdvInkGRGN1jNz21XYzVGsVktz3q2El9lr3tbFaozBHtFyf1i51jT1pPsPmCUYrR4Z+nvjo+N4ptu7LEyv5Ir5h83mF4zVH5t8i/2GM5FntsqBh9Uez+22zH+HdFw4v26Ny3oPJklmnj6hx0P6CafTBvzbZ3LkiK46GyjcR/3NyZ8x7VyFxLlaLmzgaDQQRltIon90OrlgqxUzTgl2Vi2+4sJBWrCffiM8rqA/QPfnwTLr4p/wtiOZ+JlXsc0ffBJDq6WofbK7eL0R67aeHpvktghBWJbcmzMDvjMBBNC0+Jk58lDNERYhJPkcIH5Kuw8BAoDCW3941yGPbBbM0VBEm2O6KfgXLfQJPcQlxSzlB7Z0sSp4/HUMempz4X4Tt60tpOeSd2P/h0cdJLW1lj+6C3TO14JCZGnyX+Wow+atmsdhIvfoFTwY7ajg9JMfk6sfOG9+gSmuTkWKp3zbUYwfvPJdMY+VJE54Fe9OgPkm4thknV1N6Rh220WzawwQjDkDp0FGIrFcJgJ8x2jmY9dCx+63EcLBsphx0vmNopq584osfF7r9ki92nsh2d5YQcbRLDlK1J+hknduyrfpYwPsYefRlqc6DFb49nH0fm9zmif6mN7rBXvnx3ACYDUuffwHxN7Z9nIVNzLa32zpwcHBV1YuftO8HJvOPIXm+pILpwmMQBO4w5kU3Y9ugZMfoKuig2/TmiR2qju+I/AEUBY2I0UWvY4TCchubWv42SUzV0OWLg51MuIEZVhlPoYySFtuVvikmxMLJGjFWgixm5odUoRIaBDcR/9DkOdxjXPfFNn4G7FJtU/tLeuf6tVK9CUVP7FbnYRjvRNtV0rMFSFf8c6mF8KO2CWyDmHO0GDc92xMA9OMbvR9lITxl2iYZXF8RGf2GPycfBh34mmha9jbmbU7n2aMNxMiQcnTnEAB5+nEjosIiOzuEGOphgst9E+rO7b9imBbHhn4nJHhEDjdGlYvQNMFex+zQM7wP4rXN4hWjYb495XzFCdfdYF2Rf94UY3Uv4A9Y6xxpFUG/s9veMYuV7wE9fn6VJM38MEl8HxGegrqNGh+EF0XDKHvW+IjgqnzdtbAHLwVgH+n+ZaAAjEA10lNdWnnVAfJga/6aNwzAqBLpSMVYFkdsp8eRese0UjNTn6UhdtFc8+a69s+FrZ8WYjG58oQFc9YvWA00kHhc7TtwzUexcaoD4mdQK4/0NcGSiAdTwqr0S3Nm9B1Ab0c/RCAtBagfUUyxPEJO1hZGxYuxu7FZ52Ia7wSJy4xs/RXM4Fm/vhwUDbvLi7HhrP/KYu+VmM2i7Ki7GHtsTXonjz9TuBC+54VsVgmx8qKamb+ymvrM4cbWQAtlAXLqNRZfJPaZt/aTGeDExuZ5476c0wpoAERawgrEecDK8esM9hBUDZGOAdeoY1ZAZLB1lMMrXEGMen27Mr/anjHk7loI4vBjkLIpMUOTMjT95jEr4s2N0cu1XJleY+0lYcAoWl+CX79uBy4Pbqm+vXlF9R7W0YrtmxleCzMgSlLiBMPljUoNeWEoU1oy+CCPYjjuIV7qectX+KZ3yh0M9ibmYw4U9pvZ/RRefOfRJtJNIl6feqE/dd5ea9P5zkAZVodd6PbI7U6GX6ZFPz2IwzMKvIMryPmA4ApwNUgSLkGDrFyqCq49zBCVIcMlxFcFKvoYRSLCQzCO7Eh8Y0IXu6iuEP9ibGD/GX5qoCt9M7c/idEU64Lf4Td2p4Cd5mRfoyVz53Puwqtt2GP48g/Pf06UNsEwOHIVBQzIqlkJGLer2AfgWX3qUE+HeESn2F35Ce/2yo+qYMfE1EhdTA3sOjSj+xidkGkWqKsgcAH5xSRILxiG2GY3iIjr+54/pagSBbZuWARe4tRR3c2hlconvAeVxa7bxR0lIiErqmJhFnTzSWw8karKIZhOFGg2TRYvnatWixdR+RFA0TFCaQLn9NwatvX7boG/dIZRqVx9087+cJt2MrqAY1/kW4gWuRC+AXKMP+xZxHLs/plrt6ht0HPrUP2TU3+2jI7ifhRbXkIh8fGqEhvoo3Z19On6jewJdEE76hPFJ1acWPpatFl726ZnYbVAH6Rhs9BfAZOIKIzaghApK5rH4g5j5i/xBJC5fw4BMUTQhhRma5saRIZuuQokh7kQFH8viCDgrfYJJHjyiXm0mDGQRwsSMZvO2qd1H2EqQ/EibfdELu0GOLuvDXYMcy5blVUT/dWjtZJisx96MTQbPH5mCrNURg4c5q/PZHPwe+31OEBJYisT3QiV9V6FZ5xtonPjUETpKSKHoJ2L0+fjwPuptlhloT4tojj19qoETT5DNDlzQdowx0IGDdDZrMjGDjhiYPUfVmEnoSjkacUUNm0yjGwljqDxspBDnXKhgs8Z0vpS+Didoz2EDQdIREDOhJJ19VOInEFh5BCfcj+KtkFb9wUDG8tupsfxyprH8VNrc03GOCSWsaMYezUd2RMWRaTaA0ozF1H4qraHXzjElYiSUSQ8H49SSH/8IJGw/KhtR3H9NYORK97hglWJqfwa9XdJhAaGfwq+wTvyn9cTtcapjy0e0R4rYfl7CpjP4JsdJ7PVmlcp63qv6X7SeJz7SsZ5FCc56JgCjzxWnBsUbh8meIG4wHJVrTbd2mUbaUhHRc3g+E++Ns129TtEoRmsL0U0Pd0QrcM8wx56cj0gjFCliwZSZBlNxWKRbjDja2g+i0SQXQUe9STYL1Vt57f+dZjSd57DOb5FxqoSJbYc4/znxI4xUocH3/o6BPTb4Bn7TNrgnS9vg41n6VvodnS6vOIw2kowLh6iX6wUvt20D/Hlm0+IqAa1nBvYI24rlp4l7DtM5DOdpnMPuJHtVjdog58sYw48O0SHk+pAahfLgKjZr/L/XrIU1+/FfabNGrtkBbsY2cjN26WFaZisro+yjD+4Bh5WFLAQHxog7BcX+eYNnDeqJLRXiJchJG90qEeSF2F6X0npVCtK0Pl/V+ni91k0Ye/zXocyB5qG/Ui5I3PfEB3RhteEQCVSsRxMj/5a52K//Si2xBUok/nIqmdykOj95jLjyE2L0DDfw3wVa6wEcy+PJqIeRW8XOPKrYSK5iI3m7GF1BtywhlHXESh2xViPuWRfCMtnUXp+F28A/t2yAQk2p/QiMeYvZkcUxR/RwfPlfUYqdYuWvCKWpPZu4yHqjeH19oTwOz5WyHdFrxbbnwZ/UGxOvQ1FuPR8rE6N7cBexeyAbJvGnDWRfZu4pu6HH9N0uXJB3J240/Uu3sXtwT8hhsg2AO/gT6cVrB/H2yh7Tt18l24NsK/zMX+mBELSCHE36zB59097992xss613QDTEkblimHbkApDHHj0ef5L0zicLOxsPGWF1LwPXJ+PHe7GeyY6oy3hz59wzIHtNIe62FCoKsrftMtZWnjR1HID1VqKIuP/1FjMNilYjFwRswhUBHobGyz5A/wXKLIKhE5lI42QSKK3PMcfknCoMkX4NRH0T4iex+4vZ/vZDf2GVidGDGCEdAXhXu+URaPIaigfrQQh/igLrL8imK5iRH9D1RacM8TsQFsXv/YAGGp24sQFVPwdSWo9uw2fOnsEH9RG3ANuecpZEWMhkkdrj3pC2mBilWUw8aiBjBJPEGYFuyhlhdY/Gy63u+1aRBnLXVJrJri4oY8TaSmWWdeSYxR5Yd9D5da4lqBqhc1Uj9Eqd1vuGQwt9N2rGGZlI52H3Yv10el1vWRn/nKm5Nf5CL13GGGlfpS1M9h+kHbP3oELXI9Dt02T8J38hiusbn6nVPe+TKMjUnsu69hFoKTEAuh4cH9x4b/u4mQ32wdD36EF6jPACMna12NlgWblt4TLacz99P/04UYySnfFiroonD/JHk6SOqlQdK97PeCRJjgXzxbbWOIz3n7Nzj0J7rNwixhbGra/H36KVim2nYdJ+jB4kOmKz7Yb3FSK2wRa/7T3iPjiGLj/I3CLZ3X6OaPKo2GkzVP+JxKWV203t+HOtrYSpSftEw05kWrSewFDhpfdIy47ONUVi2xlDpK76ofzqB21C3xLCo/UodppPJNHNmb5Grt2fvofWj45zIfQgXURVMcmZB43u7JvmQLd3VoweiQvQXVt7GUsdplzcvS6x98xjsfQ8dph6HLwL8RXy1SSqjVypjWhNHYEcgQQWnX9WBXEFyBL0bZc9+rEj2mgxnt+nd9ujJusBsseI5/P22AzUNtQtRt+N30OUs5O0X7ksbrrfT46nEuKk/WjrdeDPkeydg6r11YN/VjYm5FI08Dqy1oRUd6HZZxr070AH0xHovkItcgSml9rY1NpYxFh7fQSUg1uRufboldYDxJlGI8ZEIdBo939vt5TaYysEcva07x+eNSZrZo22LG7W6FHUtEJA9lhT0W6x7S8wZSRkE265l4rRkdA3MJpKHZWfm9q/y4JdsTueLSa7gIgUMKB6o+/KV2AcXiDGhkFQDcrKplsXMCd1QowN2jGLbQNZoTnowEaIsSwxahB7sijRHCB4VQSdyIVi7C4A1oGLmWOkj4d14dma0V65S4x+CtNBZJu9c94APXGMvtdX5+h0GxM/1sTh8iWDLtJhuT0G//jg6UacEJbFrQdg8rE2qfXviLlxkSZPoqY8QWvKkR+gGe/aTx61YE+w7QT2PonspLMHKBIn3hhI7OhsLC4EBeOhoxiDfsX14Ml4dD+Ofx8MJjedbO1RG5tsYzAEwAyxdAXdRh9HYs7LNaFuZDk6ryrkou0MuPEVBlPHZ7BgSPzyojRheuS2MzgLoDaueheKO86oN4bPVxzPIWjxD4GXxOokhhYgAwmyHFEQ4LlbluH+JObKwGB8OCg9EYZmEvV0OSyPp5oek6ZpCTV9+z66hz+OPCVxueYpicjtqNCKfdjsgNi2o5nfTufl8KfLsUpFsCadQFIRNKcT3J6adCY/lPs7q1l4cO7kosS+v6m2k/NOKyrqBjYTJ9W5l6cU+B+YOzSpyh2Xyu3A3MIkPdeIj0RnqlIzeu5v4h8vRoNt6y2lguykxz4Y+y9lJ0DqwH/GRYyZoZSPM+9gDADVx7e/Tb8Vxl8woc2ttxhZk8bBJo3/hCYfYk0a43WkSQfuzr4gB8Wk3Ri5U4yBA3rpy7Yx8R0aoHzyFj272bWPOMjUuveBdyj+1xq8H/AJD+uWWwrRFHridpLuZDulJ+P2d9CEPzS1V5FTO7LvMx2/avd9/gHGfW/T7Z7pwDh5HlS1fjKSPdvjYvQGSzWev5na95OHDu4u3DYEhqX19afRA8dF1GvbAEQyM3NVT3UF3mLTszxGN2LoFlGMqNFmTfYNadpkv69HwBNHZfa5196Zky/emMzGOqHxapPjpB2fH4kV4oxcGF+AKscD7fvVT5R9/qYyKdMJrZg8WSNbCvEBr3gesP3TtzLFf+8RfnAX/pP4onfoGd21YrLWGLGQ51ZUc/TLbGP2xBsQk5LzTspbRdwCOgGuOirJQUWOBVaPZDXTHIcK/4c+n7DwvbbWAaF1GHbyjrfJcgdHJEx5jq8nHxpr5KS5+k3lwT122D/ZtO0NerwcPYZPy/WjRNKbZFpRHe5BZFQbPcZV9e4bGsVsW0SDWVTMAFbz4JsZFWOP3QAquDWOz9nVdvrj9uuXxiMmfEjua28RYR/d3peFK+ujchFR2CgS/Nkrd0aWoZL2vk7sWM4nNixf2n6gFiLMKZrzfI1RA0lkDlro96B0+wGc5oym9rdxAiCba227BlIPVjYTo+mvNnXnRdstOflkJwWTvltVI6OJXwARMpr0NajIVuqRLayO5XWKyepoAQj9yHgyaR3DVQs+nR4fA/pNDFc74uuTdJeeEJwCSRKT1AT/fYYj2IcEv0AMKuO+HTgMuYkJtwHxWZM9ZGemFrzBLvZInXrpOTtts+9SzWYfJ1RCoEdofXdzJzd9a/jNu27Wf7fRCbchLUpv/yxtsbvboN/i7wzqzUHn60xiuoz0kMjFdRGbdHwfafe6iGLv3Uvd9Pw9rCVlIXoyPvoNZRtg6Ot0fPRkK6c35hzl9Gbb63RDmWA+vrVKeAYfRI9/ey/tveIcegiDl/XE57yuWiS49gwewtzGTi+RDg9h1mYpp6ide7WNP5irNF7NGieY4bhR8jXCL2t8Uy5tfEMunpftVTV++LXBxuezxpEOG3el7/ISZS3eQ+esMVA20Xg2bQOOEE3ZQ+eP468C0Wwg6iPnsKtSp0rPFtNzAdSYGBuxs3jwXICgetqJ1pRzgWCO9kDyN2l75N8WdG2qL0JbncdafZA8CzRiEdcqQUGrqC6l1X25mtOIe1VG9g291uZnUgnqSxFLOY1YiQbRvYf2XysCjwJV302Zyr/7Ki2PDCrld2Of3sfK48894w2vUVP2slR+je6ZOvbQI080LXaKhV8v8BTr/MdlvPhhxYxYQ/j1Aht6Oc1T/OwcnqLTkNlEn3qFnD0tm6iyMefEi7OxL+VSrntFp7ffeJXr7cdfUW1b3Pryec+eGl/9x86exGgNPXpqzFKOnpZnZTh6ujFtcrjkHJPDWdycvE+nFya9THrhdYtqzB2wXOSY+zK98PhLOmOm9hVuzJhfVvXC3hfP2wsHX/6SvTDcoPRCliFDLxxKG2//oz/eEo8LzKsqZ4D3vsCdAU54iZ0BHjqtnAEeOJ3hDPDJtDY3nGOM+zOpe+aL9NgluRvVnl14W5Wwbc83qoS+6zJRD2HUeym1+rQQfZfxpcyTy54XaMHHoGDCdJr8PqZ6KW70FtmjZ+2xO8wYJ0wmccLVac+7P8l+NbJ8N55SzjPT6PKOonOV+QErM5GWKWJlCs9Vpp2V+ayHlKFBd+xKLDKBFBmb2gmf/SJ11j2ENI/u/uwouq36DvVuwxJ+6ZYDS7ecPruK4BaeYDgQDO+zqQgW8gSjgWB03xwu3PyQPAZXbon7ULVvqx+BO32W7hoY44sw92N17ki2p1AYt2JuFoB8/D64fqyDPqqN3URM8gl6Dl5k6vg3op1x9ljAKFb2yS3Vz6Ii+yr0l65Ufm7YX0M4/x3osG/sJkdsci0M3wl2XHCMtbMg2FH5UeS/8McRK3YRm6Oa3o4PzUZegeaxc4zYEzfuoiY2fRffI0Yu2tbs79WL0dOp6OxbxvhwejRxW+KvPcQ+tfmoPWxoRw+je2knKky3vmcZ/aMK/Y/OTb+R0Tcq9Gt28scjm+riRyAnvnMXcgfrU+ieaLJ6qT16onqJPfpWdYOj8+rgGLOwROyc0gppvWPSIVjDdZ/Jxl/Wxn+yg66Ar0ztb0aPwIpvLtSRHP1nUKkBejFyhOhshaK07Ry/n29nv9FlP8nF+yimNrpbpoblRo9fWBVpanKHhKmRcGgquf0H722cGlwnNwf8ZSXlUxs9YXlK0Ola41ztDhN8yOln+R7XVLwYJTzV3+gMhZzrSpqDQaEl4Gk0Fzv9Af86XyASNvudPncYKnBPmjVLKTZrFik3axYreIM34F993QWXCoabnUE3KXST+aZZs/D2J4/T67nLLTWFAj7J3RoMFbsC/rBstpknTjLf1mC+0UybCNbD13+kneugqgsv6Y/4guuk1cjIDRdXxkPKUOb/17R4nZnp0jzxpguvAJiUPasjQCf5AyEf6YBGKez1uNw3rfiyFjWoDGJVvHKqgc3/z5Q6a1Yg6A455UDoRmaYWoHASqtDq8HE/t9xuUKwT11kpox6An4z/E8u+2k0N3m8biE0WZgHqXk8kvjNTYGQGW978/hXC/yFUrNm4f1OKEQo4kI5vV6zPyCbW8A+GgXzUA1xOLIKvgoeP8k3ez0yNO8ltSNjxZPMaz1ysxmvSzJbS2ddI9QEIt5G/zUy4wI5Ul13t9A6TZrvWDSn2iFJCyVrhSL8dCK7tXSp0xtx2/CGL9uF0JfVy05UcqNS5Nz0lTblCifbhfFTNgck4wsVsnttqr5RpbovJ3W/B8svZPnBb1RlzO9dRvGbdPK3sPwtmvxz8zvTvojT3QXIN8Pmb/GEAn6f2y9rSqr5MS/PzI+S38/wK5dXZbyPV9EDxrSkHpZq73lM3euxXE3fex76PZr6C+vV9IYrsq9vZ3fkFP0pmcTNwa1dyeRuWNXthxR/s7S7O5nElYrxQDKJD2UOHEwmH8SFeDyZ7MIHLr5IJvFE+cETyWQppM0nk0m8CeNBSDdk4W/rk8nH8LErSPHxq+KBZLIXUvw9bTG7pEi5K8dw12LB0FpouGJ4vnGTIb9wNLuHxgq88PenZKand74gfdWzwDvWXVA4r6DoZtOwtcYNwuwx119bZpnA37+dfVedg9SQn41XUGYr9ZSz+2OegHZnXy4IOd47qoTqgsI5BUVzCsxzCornFJRWF1TML+jPbcvfmNeZ+3DOI9kPZJFyt2M/7k8mD0P7OY9KmcvtyU4r9yje//Ie6Bhv1jKvzFRubsFmQ1o5fIJ5w+Fk8ifDodzLKzO311WgKjc6Jb9af2OZbvZ8lkziwz3CnILC6oKiuQWlbdkPZ1G94D1XddDne8mFtGltVRdUqZpK9ZeM9wVBua+zcvhsAOLxZz3C8WTyag0eH4ApyoDHk4zSDHh8VjYONjye4ZV7yK+D/CqgdwtUnkeybAVFD2fbCsydObaC4o25YkHpA3liQUVbfm1BlRclADmKiUwgGchnpPyjbUM9WZoxlsz+6f0bNgjZ/5aF123glSa/xLbvZEAXAnmgS7yc5EW84QR3RPDnK+9hztIsSjYLh+AaBsxBYAMD5pvYjehIvg+vbCnMobdm9SJwRQ6t7RACJQCcVS5Mvw5oGnFTAivYBMB85UqwdwrodTirsco/mOjdX4TsGfhTpEj4+kh669VI/DN0FL3ySEbADn9uVGp74FJ6uddYFG7rZbRM4eVM3EhWSk8d96Ge7jeUGOjtYaQG/CmBrOjySQP1RfuxED5+glweQOALA+WS5ORl0WuNSM50/s5f3KZGXn6XzW6TRmu4C8mQj28aUrz8gvDyY8MUdrPXD5GhbzLgtwj8nt1Z1gOAYT9zkq8hMJHduvsOkuGtDyYD13wBu2/f4MmifVaB1/jI2VTmWxDYm0uv6XIgcCyXSnYK/3wBf27PVr0dIJn9xn1C9h4CvKvI+S6zLnzCSRjC9PkfWFBmwBkE/tNA7wnLQrLPDbSMCQG8k8OoNFTIrheuQtOZkEvvnroZgYW53EVXym3qczDn3xlZFwIvAfDfSm33D6GKG4N/jMMosBkNdhT8iRmErz5ffb76fPX56vPV56vPV5+vPl99vvp89Tn/p4u9v62XvS9k81j1vpdBJ307Vw33auAzDFbunDYX0XqVu6Z3sH0z5W5l5T1iyp3Kyl3SY1gaZ/nKPpNyV/bxs8kApo9l0fqUO7e7hlA49a6zbAord2a/xjKUu7KVu58v1egndec3u5dZWXsvy1Xvmyl3eit3S+8eVaXCd42sUvGt/C51iKb9s0kqj5nRJxms8NHP4E2FVf+rdpJ6j53ms5T1axNLW1j6AEu/z9LHWfpHlu5i6dssPczSEyzNY/upl7F0IktnsHQeS5eytImlLSx9gKXfZ+njLP0jS3ex9G2WHmbpCZbmsff/XMbSiSydwdJ5LF3K0iaWtrD0AZZ+n6WPs/SPLN3F0rdZepilJ1iax8bjZSydyNIZLJ3H0qUsbWJpC0sfYOn3Wfo4S//I0l0sffuKzHY0v6Zmlrl4yaqIX46Yy0sqSsqnTIsQyHqPtbyktLykfBLFC4zI5XX6V5tb3KEwnhqVlUwvKZ1STotMu0cORcLyumnmYtm5Ojx1sc1hq663SWXTS6c24WszJpmL8WinEQ+bHI6ltbT4JEEoCa/zyc5VkMohmjYr3zx+2R0KCiX+gOwuqZ5jnwJVM2i1P1KyKuLxNk7xNAoEanaGm4WSxnV+qI+mcojmMIZVgAR5IbfXiYTsW9ArY5Me+Cu7W+Ev8O2BvECjU3YKJe5mqSnk9Lml5sbQIASVulzslSWSTF6PROqQyGkdrUP5fqcrRBhz+jwuKBeQyR/aLm1jVTgslLgCPjxD+dLj+QrmqxV/NvheTUHlZ7XzgPK5SlC/K2HwvZXM32voczSwVVNeZuVlhrCcpzzuQ58AX6iUV/z/YwzRyPC5mvlC+Sxkvj9LMz8ojraLzQ95THajxk8vZaRZmvmma4h6ftHT3x3MtyvlFX++iU18mzT8a14fKqxhc4UCK/OFmb1sYbMwyH92BvnvYjrN0sxPXSPV85NWf4r87Zryyny3e5R6fsxlMYC2/MPC4LtW+fjAXKSe9/X6P6opX8XKV7Hym7PV9IWa9FFNeSX+6WUByAczM5dXPj/UlFfimR316nldj//NmvG3h5Xfw8ovyz93+09oyg++/3Wwf87V/h815bew8ltY+Wc1hzJa++nSlMfjPJoyf5J97vbxdoUCLq4ZfJ9sZnm17eOPTkxceSU+jPsy02vhI4z/VFzFyvdfYPlj3Nji4yPl/b+KYvI05RW5BjTtK+/nGQicu30lPaMpr8SnQpDZs+Hc5fH8jC/fy97r0PvNC9P/cHYokmqfveenn5U3avpfOx+MZO2XavBK+Qd05h8lHSmo38ejfFpCzH8Yzu1/edvlP3XfoqnIXnKDLzCozeC/hui0/9hDNL1m1LnbP9cnG6iV+ViNz0rNs2p8dmr+VONzUvOiGp87ON+p8HmpeUyNz8+43sgGrSjzjho/JDWfqPFDU/OEGj8s5f/V+OEpv67Gj0j5azW+IOWH1XhTyr+q8YUpv6nGj0z5QzV+VMrPqfGXpPyXGj865ZfU+EtT/kaNvyzjOisbVpWKf1DjiwbHvQp/eWo8q/GD70FV469IwxmIz/40qcXTd/Gk6+F6hsfHM/hPLcPj4xf8R2L4lzX4b5JxOdi/yruLHiI8jRFyNe9ZfZrRK8/hXM35d8Qrz/8o+CsNFK88v6O8e2kxwxfWUfyjrIH1DN+rqec/GX7LLRS/V/HLDG+eRfF1Q4RUXIr4YA3F/4RtjOCJPeJLZ7B1IHMqH2RTeXM08n5K8KbUc0iKPxqfQ/FBDb6B4bdo8N9meOU5KgX/J4bfoMEnGH6Tpp6v5bL62XNkyjuW5jO88vya8s6kuxheeS5Nwf8XwyvPfynvQPorwyvPfRUzvCmP4pXn35RnmW5keOE2Nb2P4TcvV+M3M/weDf7lvMz2/w6hTx+/H+axftTsn51i+JUa/PB8itfut03Ip/1u0PS7leDT/ckyVk+Xpp5GQp/ul/TkaiP0I4Vmzbj+Tn5meQUd//ATQp/ul35H4tlL0vjfwfBaPt8h9aT7w958jCXS/Vtffub3SA81ZsbPIHjQG/MbSiwwj+ENGn3WGjO/R3qjTv2/0cHvN2Z+D3lcB/93nXoKh+i8T14HL+rg1xF8+rx5rw79z3XwW3XwL+ngj+jgLxuaGT9TB3+LDv4uHfwvAD8ha4RQxeRV9n+fHZr5fd1JnXrwwZtM7/GeOSxzP9YPw5h1MA5R1kOrhmWu/z4d/Pd08F06+Dd1+PlkGMb46ePotE491wzP/L50x/DM9JHhmd9n/qPhmd/rvg3psy4X+jX8vKhT/5Hhmd+LbhiRmf7KEbT+uKb+yTr0s0dQP1DH+svN8It06H+lg+8ekfl99e/r0BsKkGZMmh5GFGSmLy7I/N77FTr0d+vgf6aD366D/7Ags12dYvRbxqjtZJwpcz1lOvj1OviHdfCPm6jejBG13n6pQ9+vg88ppPpU3jer+PmbCjPTNxYyO5TVfuN7OvS/KaTjTtu/Wxl9lWZds1+nnqkjM+Pn6ODv0MG36OAfHUnlEjRxyK916Ht08Ed08Gd08GNH0XHXz+bf2eyAcDzBZ1gnTg0FAvLU4Dqn7Ao0ukNTg6HAKq/bF57aGJxqm4ovoS4rcQWD5CXU/E58aRrGmoaZloYpE1K/cghHVkl2abABabnebyCsVknC4wjZ45ckR/nCgJ++I/6Cf6Iyt5S+BPxifkPyD5WZdgFlyvHHNhdEqfxK5HysRGSPF+QNNztD7kYp5G6y18szWtwuORCyL6wvlWhtZWE5hK9ur58u2Ww2hYEFF6JzLDqzKeLHGqeHg16P7PLab9ZUjZU2uLzhkH4dNlo4HEQyQDTaZjYFQmudoUZ7g2RrChLGgovqK6QLZo1oU+GtAn9J5fX43cje4kH+CNH5GKREqSrOy2TlhTOp8Ffmcwap5qZJ5R6/LNk4Hr2esAzdNUNStHludm1Y2XmZrEYm62VHhSR5AuT4TVreYL+YH3ddAL32x1cXUkTze7ALKJLhJ1DnLzX4Q6vz01aqRai/SC3VX7yW6i9eS/X/kJbqL0JL9RelpaUXqaWlF6+lpRfKvCskh+VIU1OJS5Ckm2sWSw57fYMkCTCtuVfD6HKHJNknubwwf4SFDChJagxIq72BVU6v1AjDNSw5I62CK+ALet2yu7FkRmXFtMxE0uBJtASKD60T6Gl2Y8TnWwdFOEgaPMBmpJI0b3F1rQ2cwVxglnLOvjOpF82bV29rkBqq5zhsSKGqolGNCMvOEIzyud9YWF1rrxHw6FvBLV9YH57hDAahjK1ugctXVTXfYZ9Ts2yZVFZSTpxZPRgQiNIoeZ1hWfIHZCnQREi1tJLXs8olucIRIrmQaqFhab1snc7/NnVVpMnuAqTVBdOTJIec4P/tLpyIXDablgOgmyFJcnMosFZa5WyUXMBGSxqb9YFKqRZkDrtDst1rsy2uDzRIKqqSSmBxtS/gp4yhKm9ukRazLq8B6cLY38sbvXUZqg/PDLmh7ha3LU1sLAj1NTk9XpYlTSuZVjKdak+e7kKTBMmsZcDhWk+j20/6xqZupcRqFZjioDm5whMIS/j8RrkdaGusGmrB5/R6Ay51e034u10NC7RTqMQYV6VxWB8uByUEK/GnxTDPySCgb/EC0hVaLfjXYo5cCTZAekPWasLV6pSghlaPnN6MbC0LRfyyB2zejUMTRILKwum9Pa1U6e1ABG1NCjn9q91gcGmt4cMxYA5erwQd6PP4oWk0twZoq5KaW4DaG/x1O30XanJNq91yOIMA6i6Zm9Ylkr2hVhr0Kw21NehCGsgjKpJ9kURuhZAiYXcj1TtowOfKqOqmkNudwZTC1plkIDZ5QucciSCuN80QkLnMrElaf0AMwloqoTRQV2CdTccg0Lwr3YpjLl/b7JRtLRk9SBnHuI77GGzZCrbIetSb1maDPc2UtIYB4inOkukZ2tMRoV4ud4GdpaMrUzallUhqDAekZpiEQXn44FTAm3HMoSNk0RV1YQFqhoqTymCN4LVAtkHTRaMFF18q2SAErFtQXyZ5tS7N5/b5Ai1p1oJaGuwZrXTo4s49kleFw5xFBKY3eSPh5vS+xXm4FMd9q3OVp8WKQzfswYEJxdHrgaxNAdA5lKieY5esJWWaoYRLjoxeBL0b6F7iZNBWMiifXi04jvRqkIIgOsT10hr3Oub5Mvqp9HEOKnf5ghkcBHM6IFvGzp3u8rqdsNySIXSxg/zwT4ZWNUPfHWjSmhOKQvpJLQGZ5skYvIjZlSwkNAI1kbso0kxIPW2DLepUnGnGnsnP2KQzW/SGOxhNveT2BeV14J+C0FQg5FzttmXqz1Xgv/zg8WVXs0YV5Gk+mN5bW6WgOxQOgOfwQIUtpelmc5FzA3gPtAnSY4tgfvUFGt0ZJsYM0rEZLs3RLfGvRWe42B2O+LCqmhrAl1LmZpBrXdwZJhfQ6kw2XDMEP2XBiGxzZWACbK1WArtbAx4L1gwZTDm4brDnreXqiDB9hsYYQqB+7f8AvTz/B7+cAAA='
bin = gzip.decompress(base64.b64decode(gz))
p = os.path.dirname(__file__)
pymain = os.path.join(p, "a.out")
with open(pymain, "wb") as f:
    f.write(bin)
os.chmod(pymain, stat.S_IRUSR | stat.S_IWUSR | stat.S_IXUSR)
if p == "":
    pymain = "./" + pymain
subprocess.call(pymain)


# compiled by pythran
'''
#pythran export main2()
import numpy as np
i8 = np.int64
i4 = np.int32


def solve(w, v, W):
    dp = np.empty((w.shape[0], w.shape[0] * 1000 + 1), i8)
    for i in range(dp.shape[0]):
        for j in range(dp.shape[1]):
            dp[i, j] = W + 1
    dp[0, v[0]] = w[0]
    max_v = v[0]
    for n in range(1, w.shape[0]):
        dp[n, :v[n]] = dp[n - 1, :v[n]]
        dp[n, v[n]] = min(w[n], dp[n - 1, v[n]])
        max_v += v[n]
        for j in range(v[n] + 1, max_v + 1):
            if dp[n - 1, j - v[n]] > 0:
                dp[n, j] = min(dp[n - 1, j - v[n]] + w[n], dp[n - 1, j])
            else:
                dp[n, j] = dp[n - 1, j]

    for j in range(dp.shape[1] - 1, 0, -1):
        if dp[w.shape[0] - 1, j] <= W:
            return j
    return 0

def main2():
    stdin = open('/dev/stdin')
    N, W = map(int, stdin.readline().split())
    w = np.empty(N, i8)
    v = np.empty(N, i8)
    for n in range(N):
        w[n], v[n] = map(int, stdin.readline().split())
    ans = solve(w, v, W)
    print(ans)
'''

Submission status: Accepted

Solution code:
inf = float('inf')

n, w = map(int, input().split())
e = tuple(map(int, input().split()) for _ in range(n))
wt, vt = zip(*e)
sv = sum(vt)

dp = tuple([inf] * (sv + 1) for _ in range(n + 1))
dp[0][0] = 0

for i in range(n):
    dp[i + 1][:vt[i]] = dp[i][:vt[i]]
    for j in range(vt[i], sv + 1):
        dp[i + 1][j] = min(dp[i][j], dp[i][j - vt[i]] + wt[i])

res = -1
for j in range(sv, -1, -1):
    if dp[n][j] <= w:
        res = j
        break
print(res)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
INF = 10**10
dp = [INF]*(N*1000+1)
dp[0] = 0
for i in range(N):
  w, v = map(int, input().split())
  for j in range(N*1000, v-1, -1):
    dp[j] = min(dp[j], dp[j-v]+w)

for i in range(N*1000+1)[::-1]:
  if dp[i]>0 and dp[i]<=W:
    print(i)
    break

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

N, W = na()
maxV = 10 ** 5
dp = [[10**9+7] * (maxV+1) for i in range(N+1)]  # dp[i][v] i番目までで価値がvの時の重さの合計の最小値
dp[0][0] = 0
tp = [na() for i in range(N)]
list.sort(tp, key=lambda x:x[0])
for i in range(1, N+1):
    wi, vi = tp[i - 1]
    for v in range(1, maxV+1):
        if v - vi >= 0:
            dp[i][v] = min(dp[i - 1][v], dp[i - 1][v - vi] + wi)
        else:
            dp[i][v] = dp[i - 1][v]
ans = -1
for i in range(1, N + 1):
    for v in range(1, maxV+1):
        if dp[i][v] <= W:
            ans = max(ans, v)
print(ans)

Submission status: Accepted

Solution code:
n,w_max = map(int,input().split())
w = [0]
v = [0]

for _ in range(n):
    W,V = map(int,input().split())
    w.append(W)
    v.append(V)
v_sum = sum(v)
lrg = 10**12
dp = [[lrg]*(v_sum+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
for i in range(1,n+1):
    for u in range(v_sum+1):
        if u>=v[i]:
            dp[i][u] = min(dp[i-1][u-v[i]]+w[i],dp[i-1][u])
        else:###
            dp[i][u] = min(w[i],dp[i-1][u])

ans = []
for u in range(v_sum+1):
    if dp[n][u] <= w_max:
        ans.append(u)
#print(*dp[n])
print(max(ans))

Submission status: Accepted

Solution code:
inf = float('inf')

n, w = map(int, input().split())
wv = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = tuple([inf] * (pow(10, 3) * n + 1) for _ in range(n + 1))
dp[0][0] = 0

for ind, (wi, vi) in enumerate(wv, 1):
    for v in range(pow(10, 3) * n + 1):
        if vi <= v:
            dp[ind][v] = min(dp[ind - 1][v], dp[ind - 1][v - vi] + wi)
        else:
            dp[ind][v] = dp[ind - 1][v]

for v in range(pow(10, 3) * n, 0, -1):
    if dp[n][v] <= w:
        print(v)
        exit()

Submission status: Accepted

Solution code:
N,maxW = map(int,input().split())
w,v = [],[]
for i in range(N):
    weight,value = map(int,input().split())
    w.append(weight)
    v.append(value)
maxV=sum(v)
inf = float('inf')
dp = [[inf for _ in range(maxV+1)] for _ in range(N+1)]
dp[0][0] =0
for i in range(N):
    for sum_v in range(maxV+1):
        if (sum_v -v[i]>=0):
            dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v-v[i]]+w[i])
        dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v])
res = 0
for i in range(maxV+1):
    if dp[N][i] <= maxW:
        res = i
print(res)

Submission status: Accepted

Solution code:
N, W=[int(i) for i in input().split()]
wv=[[int(i) for i in input().split()] for _ in range(N)]

max_v=0
for i in range(N):
    max_v+=wv[i][1]

dp=[[99999999999]*(max_v+1) for _ in range(N+1)]

for i in range(N+1):
    for v in range(max_v+1):
        if i==0:
            dp[i][0]=0
            break
        else:
            if v>=wv[i-1][1]:
                dp[i][v]=min(dp[i-1][v-wv[i-1][1]]+wv[i-1][0],dp[i-1][v])
            else:
                dp[i][v]=min(dp[i-1][v], wv[i-1][0])

for i in range(max_v,-1,-1):
    if dp[N][i]<=W:
        print(i)
        break

Submission status: Accepted

Solution code:
N,W =map(int,input().split())
weight,value=[],[]
for i in range(N):
    w,v = map(int,input().split())
    weight.append(w)
    value.append(v)
inf = float('inf')
dp = [[inf for _ in range(10**3*N+10)] for _ in range(N+10)]
maxv = sum(value)
#初期化
dp[0][0] =0
for i in range(N):
    for sum_v in range(maxv+1):
        if sum_v-value[i] >=0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v-value[i]] + weight[i])
        dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v])
res =0
for sum_v in range(maxv+1):
    if dp[N][sum_v] <=W:
        res = sum_v
print(res)

Submission status: Accepted

Solution code:
N, W = map(int, input().split())
dp = [10000000001] * (10**3 * N + 1)
dp[0] = 0

for i in range(N):
    w, v = map(int, input().split())
    for j in range(len(dp)-1, v-1, -1):
        if dp[j-v] + w <= W:
            dp[j] = min(dp[j-v] + w, dp[j])

for j in range(len(dp)-1, v-1, -1):
    if dp[j] <= W:
        ans = j
        break

print(ans)

Submission status: Accepted

Solution code:
INF=float('inf')
n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in [0]*n]
dp=[INF]*(sum(l[i][1] for i in range(n))+1)
dp[0]=0
for i in range(n):
    for j in range(len(dp)-1,l[i][1]-1,-1):
        dp[j]=min(dp[j],dp[j-l[i][1]]+l[i][0])
for i in range(len(dp)-1,-1,-1):
    if dp[i]<=w:
        print(i)
        break

Submission status: Accepted

Solution code:
max_v = 100001
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[float('inf') for _ in range(max_v+1)] for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
  for j in range(max_v):
    if j - wv[i][1] >= 0:
      dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
    else:
      dp[i+1][j] = min(dp[i+1][j], dp[i][j])

for i in range(max_v):
  if dp[N][i] <= W:
    ans = i

print(ans)

Submission status: Accepted

Solution code:
import sys

inf = sys.maxsize
N, W = map(int, input().split())
wvs = []
v_len = 0
for _ in range(N):
    wvs.append(list(map(int, input().split())))
    v_len += wvs[-1][1]


def chmin(x, v1, v2, diff):
    if dp[x][v1] > dp[x-1][v2]+diff:
        dp[x][v1] = dp[x-1][v2]+diff
        return True
    return False


dp = [[inf]*(v_len+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    for sum_v in range(v_len+1):
        if sum_v-wvs[i][1] >= 0:
            # 品物を選んだ場合(選ぶために必要な価値を減らした状態に重さを追加した状態と比較)
            chmin(i+1, sum_v, sum_v-wvs[i][1], wvs[i][0])
        chmin(i+1, sum_v, sum_v, 0)  # 品物を選んでない場合
max_i = 0
for i in range(v_len+1):
    if dp[N][i] <= W and max_i < i:
        max_i = i
print(max_i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, W = LI()
    wv = []
    for _ in range(N):
        wv.append(LI())


    # 横軸 v, 縦軸 n
    dp_table = [[None for _ in range(10**5+1)] for _ in range(N)]
    
    # init
    w0, v0 = wv[0]
    dp_table[0][0] = 0
    dp_table[0][v0] = w0

    # dp
    for i, item in enumerate(wv):
        if i== 0: continue
        w,v = item
        for val, weight in enumerate(dp_table[i-1]):
            if weight is not None:
                # i番目の荷物を入れないとき
                dp_table[i][val] = min(dp_table[i][val], weight) if dp_table[i][val] is not None else weight
                # i番目の荷物を入れるとき
                dp_table[i][val+v] = weight + w

    v  = 10**5
    for w in reversed(dp_table[N-1]):
        if w and w <= W:
            print(v)
            break
        v -= 1


main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict
import sys,bisect,math,itertools,string,queue
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n,w = inpl()
ww = [0] * n
vv = [0] * n
for i in range(n):
    ww[i],vv[i] = inpl()
dp = [[mod for i in range(sum(vv)+1)] for j in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(sum(vv)+1):
        if j >= vv[i]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-vv[i]]+ww[i])
        else:
            dp[i+1][j] = dp[i][j]
for i in range(sum(vv)+1)[::-1]:
    if dp[n][i] <= w:
        print(i)
        break

Submission status: Accepted

Solution code:
def main():

    N, W = map(int, input().split())
    goods = []
    tot_v = 0
    for _ in range(N):
        w, v = map(int, input().split())
        goods.append([w, v])
        tot_v += v
    dp = [[float('inf') for _ in range(tot_v+1)] for _ in range(N+1)]
    dp[0][0] = 0

    max_v = 0
    for i in range(N):
        w, v = goods[i]
        for j in range(tot_v+1):
            if j-v >= 0:
                dp[i+1][j] = min(dp[i][j], dp[i][j-v]+w)
            else:
                dp[i+1][j] = dp[i][j]

            if dp[i+1][j] <= W:
                max_v = max(max_v, j)

    return max_v

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import numpy as np
N,W = map(int,input().split())
l = []
for i in range(N):
  y,x =  map(int,input().split())
  l.append((x,y))
V = sum([x[0] for x in l])
dp = np.full((N+1,V+1), np.inf)
dp[0][0]=0
for i in range(N):
  v = l[i][0]
  w = l[i][1]
  dp[i+1]=dp[i]
  dp[i+1][v:] = np.minimum(dp[i][v:],dp[i][:V-v+1]+w)
i = V
while True:
    if dp[N][i] <= W:
      print(i)
      break
    i -= 1

Submission status: Accepted

Solution code:
N,W = list(map(int, input().split()))
m = []
v = []
for i in range(N):
    a,b = map(int, input().split())
    m.append(a)
    v.append(b)

sum_v = sum(v)
dp = [[10**15 for i in range(sum_v+1001)]for j in range(N+1)]
for i in range(N):
    dp[i][0] = 0
    for j in range(sum_v+1):
        if j != 10**15:
            dp[i+1][j+v[i]] = min(dp[i][j+v[i]],dp[i][j] + m[i])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

for i in range(sum(v)+1):
    if  dp[-1][sum(v)-i] <= W:
        print(sum(v)-i)
        break