program ddd
implicit none

integer(8) :: n, w, i, j
integer(8),allocatable,dimension(:) :: g, v, dp

read*, n, w
allocate(g(n))
allocate(v(n))
allocate(dp(0:w))
do i=1,n
read*, g(i), v(i)
end do
dp=0

do j=1, n
 do i=w,0,-1
 if(i>=g(j)) then
 dp(i)=max(dp(i),dp(i-g(j))+v(j))
 end if
 end do
end do

write(*,'(i0)') dp(w)

end program
; ModuleID = 'FIRModule'
source_filename = "FIRModule"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

@_QFEdp.0 = internal unnamed_addr global ptr null
@_QFEdp.7 = internal unnamed_addr global i64 1
@_QFEdp.8 = internal unnamed_addr global i64 0
@_QFEg.0 = internal unnamed_addr global ptr null
@_QFEv.0 = internal unnamed_addr global ptr null
@_QQcl.b2d0ca14501e15fca1672fc92bf5796a = linkonce constant [73 x i8] c"/home/ubuntu/Downloads/TheStack_IR/Collated/Fortran/Source_5174/source.f\00"
@_QQcl.16373402fa3425c6e46827601abb88fa = linkonce constant [76 x i8] c"array left hand side must be allocated when the right hand side is a scalar\00"
@_QQcl.28693029 = linkonce constant [4 x i8] c"(i0)"
@_QQEnvironmentDefaults = local_unnamed_addr constant ptr null

; Function Attrs: mustprogress nofree nounwind willreturn allockind("alloc,uninitialized") allocsize(0) memory(inaccessiblemem: readwrite)
declare noalias noundef ptr @malloc(i64 noundef) local_unnamed_addr #0

define void @_QQmain() local_unnamed_addr {
  %1 = alloca i64, align 8
  %2 = alloca i64, align 8
  %3 = tail call ptr @_FortranAioBeginExternalListInput(i32 -1, ptr nonnull @_QQcl.b2d0ca14501e15fca1672fc92bf5796a, i32 7)
  %4 = call i1 @_FortranAioInputInteger(ptr %3, ptr nonnull %1, i32 8)
  %5 = call i1 @_FortranAioInputInteger(ptr %3, ptr nonnull %2, i32 8)
  %6 = call i32 @_FortranAioEndIoStatement(ptr %3)
  %7 = load i64, ptr %1, align 8, !tbaa !3
  %8 = call i64 @llvm.smax.i64(i64 %7, i64 0)
  %9 = shl i64 %8, 3
  %10 = call ptr @malloc(i64 %9)
  store ptr %10, ptr @_QFEg.0, align 8, !tbaa !7
  %11 = call ptr @malloc(i64 %9)
  store ptr %11, ptr @_QFEv.0, align 8, !tbaa !7
  %12 = load i64, ptr %2, align 8, !tbaa !3
  %13 = add i64 %12, 1
  %14 = call i64 @llvm.smax.i64(i64 %13, i64 0)
  %15 = shl i64 %14, 3
  %16 = call ptr @malloc(i64 %15)
  %17 = icmp ugt i64 %12, 9223372036854775806
  %18 = zext i1 %17 to i64
  store ptr %16, ptr @_QFEdp.0, align 8, !tbaa !7
  store i64 %18, ptr @_QFEdp.7, align 8, !tbaa !7
  store i64 %14, ptr @_QFEdp.8, align 8, !tbaa !7
  %19 = icmp sgt i64 %7, 0
  br i1 %19, label %.lr.ph, label %._crit_edge

.lr.ph:                                           ; preds = %0, %.lr.ph
  %20 = phi i64 [ %29, %.lr.ph ], [ 1, %0 ]
  %21 = call ptr @_FortranAioBeginExternalListInput(i32 -1, ptr nonnull @_QQcl.b2d0ca14501e15fca1672fc92bf5796a, i32 12)
  %.unpack429 = load ptr, ptr @_QFEg.0, align 8, !tbaa !7
  %22 = add i64 %20, -1
  %23 = getelementptr i64, ptr %.unpack429, i64 %22
  %24 = call i1 @_FortranAioInputInteger(ptr %21, ptr %23, i32 8)
  %.unpack441 = load ptr, ptr @_QFEv.0, align 8, !tbaa !7
  %25 = add i64 %20, -1
  %26 = getelementptr i64, ptr %.unpack441, i64 %25
  %27 = call i1 @_FortranAioInputInteger(ptr %21, ptr %26, i32 8)
  %28 = call i32 @_FortranAioEndIoStatement(ptr %21)
  %29 = add nuw i64 %20, 1
  %exitcond.not = icmp eq i64 %20, %7
  br i1 %exitcond.not, label %._crit_edge.loopexit, label %.lr.ph

._crit_edge.loopexit:                             ; preds = %.lr.ph
  %.unpack.pre = load ptr, ptr @_QFEdp.0, align 8, !tbaa !7
  %.unpack354.unpack.unpack356.pre = load i64, ptr @_QFEdp.8, align 8, !tbaa !7
  br label %._crit_edge

._crit_edge:                                      ; preds = %._crit_edge.loopexit, %0
  %.unpack354.unpack.unpack356 = phi i64 [ %.unpack354.unpack.unpack356.pre, %._crit_edge.loopexit ], [ %14, %0 ]
  %.unpack = phi ptr [ %.unpack.pre, %._crit_edge.loopexit ], [ %16, %0 ]
  %.not = icmp eq ptr %.unpack, null
  br i1 %.not, label %32, label %.preheader

.preheader:                                       ; preds = %._crit_edge
  %30 = icmp sgt i64 %.unpack354.unpack.unpack356, 0
  br i1 %30, label %.lr.ph455.preheader, label %.loopexit

.lr.ph455.preheader:                              ; preds = %.preheader
  %31 = shl nuw i64 %.unpack354.unpack.unpack356, 3
  call void @llvm.memset.p0.i64(ptr nonnull align 8 %.unpack, i8 0, i64 %31, i1 false), !tbaa !3
  br label %.loopexit

32:                                               ; preds = %._crit_edge
  %33 = call {} @_FortranAReportFatalUserError(ptr nonnull @_QQcl.16373402fa3425c6e46827601abb88fa, ptr nonnull @_QQcl.b2d0ca14501e15fca1672fc92bf5796a, i32 14)
  %.unpack415.unpack.unpack = load i64, ptr @_QFEdp.7, align 8, !tbaa !7
  %34 = icmp eq i64 %.unpack354.unpack.unpack356, 0
  %35 = select i1 %34, i64 1, i64 %.unpack415.unpack.unpack
  store ptr null, ptr @_QFEdp.0, align 8, !tbaa !7
  store i64 %35, ptr @_QFEdp.7, align 8, !tbaa !7
  store i64 %.unpack354.unpack.unpack356, ptr @_QFEdp.8, align 8, !tbaa !7
  br label %.loopexit

.loopexit:                                        ; preds = %.lr.ph455.preheader, %.preheader, %32
  %36 = load i64, ptr %1, align 8, !tbaa !3
  %37 = icmp sgt i64 %36, 0
  br i1 %37, label %.lr.ph460, label %._crit_edge461

.lr.ph460:                                        ; preds = %.loopexit
  %.unpack371 = load ptr, ptr @_QFEg.0, align 8
  %.unpack391.unpack.unpack = load i64, ptr @_QFEdp.7, align 8
  %.unpack396 = load ptr, ptr @_QFEv.0, align 8
  br label %38

38:                                               ; preds = %.lr.ph460, %._crit_edge458
  %39 = phi i64 [ 1, %.lr.ph460 ], [ %65, %._crit_edge458 ]
  %40 = load i64, ptr %2, align 8, !tbaa !3
  %41 = icmp ult i64 %40, 9223372036854775807
  br i1 %41, label %.lr.ph457, label %._crit_edge458

.lr.ph457:                                        ; preds = %38
  %.neg = add nuw nsw i64 %40, 1
  %42 = add i64 %39, -1
  %43 = getelementptr i64, ptr %.unpack371, i64 %42
  %44 = add i64 %39, -1
  %45 = getelementptr i64, ptr %.unpack396, i64 %44
  br label %46

46:                                               ; preds = %.lr.ph457, %61
  %47 = phi i64 [ %.neg, %.lr.ph457 ], [ %63, %61 ]
  %48 = phi i64 [ %40, %.lr.ph457 ], [ %62, %61 ]
  %49 = load i64, ptr %43, align 8, !tbaa !3
  %.not383 = icmp slt i64 %48, %49
  br i1 %.not383, label %61, label %50

50:                                               ; preds = %46
  %51 = sub i64 %48, %.unpack391.unpack.unpack
  %52 = getelementptr i64, ptr %.unpack, i64 %51
  %53 = load i64, ptr %52, align 8, !tbaa !3
  %54 = add i64 %49, %.unpack391.unpack.unpack
  %55 = sub i64 %48, %54
  %56 = getelementptr i64, ptr %.unpack, i64 %55
  %57 = load i64, ptr %56, align 8, !tbaa !3
  %58 = load i64, ptr %45, align 8, !tbaa !3
  %59 = add i64 %58, %57
  %60 = call i64 @llvm.smax.i64(i64 %53, i64 %59)
  store i64 %60, ptr %52, align 8, !tbaa !3
  br label %61

61:                                               ; preds = %50, %46
  %62 = add nsw i64 %48, -1
  %63 = add nsw i64 %47, -1
  %64 = icmp sgt i64 %47, 1
  br i1 %64, label %46, label %._crit_edge458

._crit_edge458:                                   ; preds = %61, %38
  %65 = add nuw i64 %39, 1
  %exitcond462.not = icmp eq i64 %39, %36
  br i1 %exitcond462.not, label %._crit_edge461, label %38

._crit_edge461:                                   ; preds = %._crit_edge458, %.loopexit
  %66 = call ptr @_FortranAioBeginExternalFormattedOutput(ptr nonnull @_QQcl.28693029, i64 4, ptr null, i32 -1, ptr nonnull @_QQcl.b2d0ca14501e15fca1672fc92bf5796a, i32 24)
  %.unpack359 = load ptr, ptr @_QFEdp.0, align 8, !tbaa !7
  %.unpack366.unpack.unpack = load i64, ptr @_QFEdp.7, align 8, !tbaa !7
  %67 = load i64, ptr %2, align 8, !tbaa !3
  %68 = sub i64 %67, %.unpack366.unpack.unpack
  %69 = getelementptr i64, ptr %.unpack359, i64 %68
  %70 = load i64, ptr %69, align 8, !tbaa !3
  %71 = call i1 @_FortranAioOutputInteger64(ptr %66, i64 %70)
  %72 = call i32 @_FortranAioEndIoStatement(ptr %66)
  ret void
}

declare ptr @_FortranAioBeginExternalListInput(i32, ptr, i32) local_unnamed_addr

declare i1 @_FortranAioInputInteger(ptr, ptr, i32) local_unnamed_addr

declare i32 @_FortranAioEndIoStatement(ptr) local_unnamed_addr

declare {} @_FortranAReportFatalUserError(ptr, ptr, i32) local_unnamed_addr

declare ptr @_FortranAioBeginExternalFormattedOutput(ptr, i64, ptr, i32, ptr, i32) local_unnamed_addr

declare i1 @_FortranAioOutputInteger64(ptr, i64) local_unnamed_addr

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i64 @llvm.smax.i64(i64, i64) #1

; Function Attrs: nocallback nofree nounwind willreturn memory(argmem: write)
declare void @llvm.memset.p0.i64(ptr nocapture writeonly, i8, i64, i1 immarg) #2

attributes #0 = { mustprogress nofree nounwind willreturn allockind("alloc,uninitialized") allocsize(0) memory(inaccessiblemem: readwrite) "alloc-family"="malloc" }
attributes #1 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }
attributes #2 = { nocallback nofree nounwind willreturn memory(argmem: write) }

!llvm.module.flags = !{!0, !1, !2}

!0 = !{i32 2, !"Debug Info Version", i32 3}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{!4, !4, i64 0}
!4 = !{!"any data access", !5, i64 0}
!5 = !{!"any access", !6, i64 0}
!6 = !{!"Flang Type TBAA Root"}
!7 = !{!8, !8, i64 0}
!8 = !{!"descriptor member", !5, i64 0}
