Sasha reaches the work by car. It takes exactly k minutes. On his way he listens to music. All songs in his playlist go one by one, after listening to the i-th song Sasha gets a pleasure which equals ai. The i-th song lasts for ti minutes. 

Before the beginning of his way Sasha turns on some song x and then he listens to the songs one by one: at first, the song x, then the song (x + 1), then the song number (x + 2), and so on. He listens to songs until he reaches the work or until he listens to the last song in his playlist. 

Sasha can listen to each song to the end or partly.

In the second case he listens to the song for integer number of minutes, at least half of the song's length. Formally, if the length of the song equals d minutes, Sasha listens to it for no less than <image> minutes, then he immediately switches it to the next song (if there is such). For example, if the length of the song which Sasha wants to partly listen to, equals 5 minutes, then he should listen to it for at least 3 minutes, if the length of the song equals 8 minutes, then he should listen to it for at least 4 minutes.

It takes no time to switch a song.

Sasha wants to listen partly no more than w songs. If the last listened song plays for less than half of its length, then Sasha doesn't get pleasure from it and that song is not included to the list of partly listened songs. It is not allowed to skip songs. A pleasure from a song does not depend on the listening mode, for the i-th song this value equals ai.

Help Sasha to choose such x and no more than w songs for partial listening to get the maximum pleasure. Write a program to find the maximum pleasure Sasha can get from the listening to the songs on his way to the work.

Input

The first line contains three integers n, w and k (1 ≤ w ≤ n ≤ 2·105, 1 ≤ k ≤ 2·109) — the number of songs in the playlist, the number of songs Sasha can listen to partly and time in minutes which Sasha needs to reach work. 

The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 104), where ai equals the pleasure Sasha gets after listening to the i-th song.

The third line contains n positive integers t1, t2, ..., tn (2 ≤ ti ≤ 104), where ti equals the length of the i-th song in minutes.

Output

Print the maximum pleasure Sasha can get after listening to the songs on the way to work. 

Examples

Input

7 2 11
3 4 3 5 1 4 6
7 7 3 6 5 3 9


Output

12


Input

8 4 20
5 6 4 3 7 5 4 1
10 12 5 12 14 8 5 8


Output

19


Input

1 1 5
6
9


Output

6


Input

1 1 3
4
7


Output

0

Note

In the first example Sasha needs to start listening from the song number 2. He should listen to it partly (for 4 minutes), then listen to the song number 3 to the end (for 3 minutes) and then partly listen to the song number 4 (for 3 minutes). After listening to these songs Sasha will get pleasure which equals 4 + 3 + 5 = 12. Sasha will not have time to listen to the song number 5 because he will spend 4 + 3 + 3 = 10 minutes listening to songs number 2, 3 and 4 and only 1 minute is left after that. 
1 1 2000000000
1
2
 28 3 2099
768 115 416 934 926 65 802 980 551 213 335 202 784 914 46 609 34 492 985 740 521 894 648 155 925 436 428 25
460 467 84 159 238 484 131 47 464 389 151 225 202 15 172 81 185 145 79 151 69 75 188 109 52 396 2 85
 10 2 88
126 607 637 147 703 805 285 761 471 646
14 27 7 19 2 20 16 30 28 3
 16 1 100
812 442 141 173 282 775 696 497 509 144 722 781 830 361 625 231
15 27 6 10 2 2 6 11 14 7 28 31 16 31 28 3
 40 8 6594
825 691 980 206 454 751 248 71 301 265 177 34 924 937 868 66 755 758 733 566 893 504 688 49 595 116 649 675 280 212 93 630 157 12 919 553 295 118 260 1
341 454 745 508 605 613 164 283 715 327 252 378 382 101 682 439 18 751 246 616 564 672 58 521 348 746 85 511 43 159 357 623 222 759 347 651 256 570 23 604
 26 2 2206
232 545 542 698 14 253 728 659 439 484 827 303 206 376 972 114 693 902 214 611 815 519 678 805 845 288
123 496 604 60 237 592 492 393 174 224 314 318 303 147 82 11 377 371 478 221 443 250 528 517 549 289
 14 2 312
64 131 657 915 428 567 72 533 315 426 706 574 194 346
34 32 45 41 25 18 35 17 36 8 28 29 54 19
 11 2 100
541 775 860 90 917 345 414 207 786 475 314
43 43 4 61 15 71 62 11 16 29 66
 9 3 155
501 379 711 137 269 236 120 942 454
20 20 33 29 29 35 33 28 29
 3 1 5
2 5 3
4 4 5
 17 1 67
242 665 270 736 578 275 8 338 804 797 679 297 199 673 612 153 349
16 24 2 8 5 2 9 20 21 3 14 5 6 25 4 8 12
 40 26 3068
546 332 883 700 159 511 541 428 706 360 733 110 220 809 648 767 919 839 345 349 182 868 950 307 554 524 770 417 735 656 938 969 724 174 824 379 311 422 891 25
199 431 169 52 420 472 120 225 366 167 29 225 310 486 468 86 100 472 62 79 196 113 101 275 41 416 287 171 385 394 472 20 50 197 256 246 30 139 362 99
 17 2 148
939 428 704 123 74 458 599 928 545 556 396 894 210 387 195 404 361
55 43 57 49 42 64 9 39 26 10 22 53 35 52 5 33 19
 34 9 2108
109 546 39 725 177 954 20 159 837 691 627 373 498 87 207 235 693 686 681 347 73 641 731 576 459 632 997 19 212 933 931 778 635 135
570 45 468 196 32 157 612 221 850 547 593 632 776 205 302 551 346 565 94 236 772 551 817 221 829 554 829 284 3 151 835 62 30 372
 32 11 3515
565 695 895 79 234 32 322 46 650 166 286 312 166 610 21 967 618 24 61 314 228 977 367 580 737 258 601 236 513 531 221 580
672 19 727 893 429 799 536 629 205 820 866 584 46 641 67 313 830 776 46 106 25 240 703 403 320 639 73 187 179 592 16 150
 31 10 471
785 637 518 257 957 866 438 173 381 549 1 624 286 323 903 488 366 414 695 728 226 49 377 663 850 230 733 102 760 960 218
30 53 89 16 96 4 37 34 34 73 97 73 5 87 58 46 77 19 51 68 27 87 7 4 48 99 88 91 55 71 96
 1 1 1
1
2
 1 1 5
3
3
 12 1 286
378 288 645 293 482 978 478 225 622 451 51 758
40 56 23 57 13 7 59 25 49 64 13 6
 1 1 5
4
4

1
 9173
 3671
 4954
 12079
 5316
 5733
 2642
 2415
 5
 4061
 16296
 3918
 6307
 8444
 7721
 1
 3
 4983
 4

#include <bits/stdc++.h>
using namespace std;
struct str1 {
  int x, y;
  inline bool operator<(const str1 t) const {
    if (x != t.x)
      return x < t.x;
    else
      return y < t.y;
  }
};
set<str1> S1;
struct str2 {
  int x, y;
  inline bool operator<(const str2 t) const {
    if (x != t.x)
      return x > t.x;
    else
      return y > t.y;
  }
};
set<str2> S2;
inline int fastscanf() {
  int t = 0;
  char c = getchar();
  while (!((c > 47) && (c < 58))) c = getchar();
  while ((c > 47) && (c < 58)) t = t * 10 + c - 48, c = getchar();
  return t;
}
int u[300000], v[300000];
int i, k, l, m, n, r, s, t;
str1 tmp_;
str2 tmp;
inline void del(int i) {
  if ((*S1.find((str1){u[i], i})).y) {
    r = r - (u[i] + 1) / 2;
    S1.erase((str1){u[i], i});
    if (!S2.empty()) {
      tmp = *S2.begin();
      r = r - tmp.x + (tmp.x + 1) / 2;
      S1.insert((str1){tmp.x, tmp.y});
      S2.erase(tmp);
    }
    t = t - v[i];
  } else if ((*S2.find((str2){u[i], i})).y) {
    r = r - u[i];
    S2.erase((str2){u[i], i});
    t = t - v[i];
  }
  return;
}
int main() {
  n = fastscanf(), k = fastscanf(), m = fastscanf();
  for (i = 1; i <= n; i++) v[i] = fastscanf();
  for (i = 1; i <= n; i++) u[i] = fastscanf();
  for (i = 1, l = 0; i <= n; i++) {
    for (; l <= n;) {
      if (r + (u[l] + 1) / 2 > m) break;
      if (S1.size() < k) {
        r = r + (u[l] + 1) / 2;
        S1.insert((str1){u[l], l});
        t = t + v[l];
        l++;
      } else {
        r = r + u[l];
        S2.insert((str2){u[l], l});
        tmp_ = *S1.begin(), tmp = *S2.begin();
        if (tmp.x > tmp_.x) {
          S1.erase(tmp_), S2.erase(tmp);
          swap(tmp_.x, tmp.x), swap(tmp_.y, tmp.y);
          S1.insert(tmp_), S2.insert(tmp);
          r = r - tmp_.x + (tmp_.x + 1) / 2;
          r = r + tmp.x - (tmp.x + 1) / 2;
        }
        t = t + v[l];
        if (r > m) {
          del(l);
          break;
        }
        l++;
      }
    }
    s = max(s, t);
    del(i);
  }
  printf("%d", s);
  return 0;
}
