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)
'''


Measured memory_bytes: 82740