도적 Anna와 Bruno는 갑부의 저택에 숨어들어 보물 \(1\)부터 보물 \(N\)까지 \(N\)개를 찾았다. 이 보물을 Anna와 Bruno가 나누기로 했다. 보물 가운데 몇 개를 Anna가 갖고, 남은 보물 가운데 몇 개를 Bruno가 갖는다. 같은 보물을 두 사람이 가질 수는 없다. Anna나 Bruno는 보물을 하나도 갖지 않아도 된다. 남은 보물은 저택에 그대로 두므로, 둘 다 갖지 않는 보물이 있어도 된다. 각 보물에는 「시장 가치」와 「귀중함」이라는 두 값이 정해져 있다. Anna가 가진 보물의 시장 가치 합과 Bruno가 가진 보물의 시장 가치 합의 차의 절댓값이 \(D\) 이하이면 Anna는 공평하다고 여겨 만족한다. 한편 Bruno는 Anna보다 귀중함이 큰 보물을 갖고 싶어 한다. Anna가 만족하도록 보물을 나눌 때, Bruno가 가진 보물의 귀중함 합에서 Anna가 가진 보물의 귀중함 합을 뺀 값의 최댓값을 구하라. |
입력은 다음 형식으로 주어진다.
\(N\) \(D\)
\(X_1\) \(Y_1\)
\(\vdots\)
\(X_N\) \(Y_N\)
- 입력은 \(1+N\)줄이다.
- 첫째 줄에 정수 \(N\), \(D\)가 공백 하나로 구분되어 주어진다. 보물이 \(N\)개이고, Anna가 가진 보물의 시장 가치 합과 Bruno가 가진 보물의 시장 가치 합의 차의 절댓값이 \(D\) 이하이면 Anna가 만족함을 나타낸다.
- 이어지는 \(N\)줄 가운데 \(i\)번째 줄(\(1 \le i \le N\))에는 정수 \(X_i\), \(Y_i\)가 공백 하나로 구분되어 주어진다. 보물 \(i\)의 시장 가치가 \(X_i\)이고 귀중함이 \(Y_i\)임을 나타낸다.
- \(1 \le N \le 30\)
- \(0 \le D \le 10^{15}\)
- \(0 \le X_i \le 10^{15}\)
- \(0 \le Y_i \le 10^{15}\)
- 주어지는 \(5\)개의 입력 데이터 가운데 입력 \(1\)에서는 \(N \le 10\)을 만족한다. 입력 \(2\)에서는 \(D = 0\)을 만족한다.
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
첫째 줄에 Anna가 만족하도록 보물을 나눌 때, Bruno가 가진 보물의 귀중함 합에서 Anna가 가진 보물의 귀중함 합을 뺀 값의 최댓값을 출력한다.
Anna가 보물 \(2, 3, 5\)를 갖고 Bruno가 보물 \(1, 6\)을 가지면 시장 가치 합은 Anna \(130\), Bruno \(120\)이고 차의 절댓값 \(10\)이 \(D=15\) 이하이므로 Anna는 만족한다. 귀중함 합은 Anna \(400\), Bruno \(1600\)이어서 Bruno 쪽에서 Anna 쪽을 뺀 값은 \(1200\)이다. 이것이 최댓값이다.