送礼物

Luogu
IDLGP10484
Time2000ms
Memory512MB
DifficultyP4
折半搜索 meet in the middle
作为惩罚,GY 被遣送去帮助某神牛给女生送礼物 (GY:貌似是个好差事)但是在 GY 看到礼物之后,他就不这么认为了。某神牛有 $N$ 个礼物,且异常沉重,但是 GY 的力气也异常的大 (-_-b),他一次可以搬动重量和在 $w$ 以下的任意多个物品。GY 希望一次搬掉尽量重的一些物品,请你告诉他在他的力气范围内一次性能搬动的最大重量是多少。 ## Input 第一行两个整数,分别代表 $W$ 和 $N$。 以后 $N$ 行,每行一个正整数表示 $G_i$。 ## Output 仅一个整数,表示 GY 在他的力气范围内一次性能搬动的最大重量。 [samples] ## Note 对于所有测试数据,$1 \le N \le 46$, $1 \le W,G[i] \le 2^{31}-1$。
Samples
Input #1
20 5
7
5
4
18
1
Output #1
19
API Response (JSON)
{
  "problem": {
    "name": "送礼物",
    "description": {
      "content": "作为惩罚,GY 被遣送去帮助某神牛给女生送礼物 (GY:貌似是个好差事)但是在 GY 看到礼物之后,他就不这么认为了。某神牛有 $N$ 个礼物,且异常沉重,但是 GY 的力气也异常的大 (-_-b),他一次可以搬动重量和在 $w$ 以下的任意多个物品。GY 希望一次搬掉尽量重的一些物品,请你告诉他在他的力气范围内一次性能搬动的最大重量是多少。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10484"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "作为惩罚,GY 被遣送去帮助某神牛给女生送礼物 (GY:貌似是个好差事)但是在 GY 看到礼物之后,他就不这么认为了。某神牛有 $N$ 个礼物,且异常沉重,但是 GY 的力气也异常的大 (-_-b),他一次可以搬动重量和在 $w$ 以下的任意多个物品。GY 希望一次搬掉尽量重的一些物品,请你告诉他在他的力气范围内一次性能搬动的最大重量是多少。\n\n## Input\n\n第一行两个整数,分别代表 $W$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments